АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Задачи о кратчайших маршрутах

Пусть дан граф g = (V,X) и две его вершины a, bÎV. Имеется 4 вида задач о кратчайших маршрутах.

1° Найти длину кратчайшего маршрута из вершины a в вершину b.

2° Найти маршрут минимальной длины из a в b.

3° Найти количество кратчайших маршрутов из a в b.

4° Найти множество всех кратчайших маршрутов из a в b.

Под длиной маршрута в графе понимают количество ребер, его составляющих.

Алгоритмы решения указанных задач могут быть построены на основе волновых процессов.

Задача о кратчайших маршрутах относятся к классу P.

Задача 1°

Будем выполнять волновой процесс 1 начиная с V₀ = {a}. Завершим его в том случае, если очередное подмножество V_k будет включать вершину b. Индекс k этого подмножества и будет искомой длиной кратчайшего пути.

Ниже, в качестве примера программной реализации такого алгоритма, приведена функция dist(g,i,m) из библиотеки ALGRAPH/C++ (в несколько упрощенном варианте), которая находит длину кратчайшего маршрута из вершины i в вершину m. Если маршрут для указанных вершин отсутствует, функция возвращает значение -1.

int dist(graf g, int i, int m)

{ int a,b,j,k,Nvv,Nw, L=0, n=g.nv;

if (i==m) return 0;

if (g.p[i]==0) return -1;

byte* Vs= new byte[n];

int *vv= new int[n],

*w = new int[n];

for (k=0;k<n;k++) Vs[k]=0;

Vs[i]=1; vv[0]=i; Nvv=1;

while (Nvv)

{ Nw=0; L++;

for (j=0;j<Nvv;j++)

{ a=vv[j];

for (k=0;k<g.p[a];k++)

{ b=g.r[a][k]; if (b==m) goto mm;

if (Vs[b]==0) { Vs[b]=1; w[Nw++]=b; }

}

}

for (j=0;j<Nw;j++) vv[j]=w[j];

Nvv=Nw;

}

L=-1;

mm:

delete[] Vs; delete[] vv; delete[] w;

return L;

}

Задача 2°

Алгоритм поиска кратчайшего пути следует из свойств 2,3 волнового процесса 2.

Задача 3°

Выполним волновой процесс 2. В результате получим последовательность подмножеств вершин V'₀, V'₁,..., V'_k, при этом V'₀ = {a}, V'_k = {b}. Пронумеруем вершины в каждом из подмножеств независимо. Каждой вершине из указанных подмножеств припишем два индекса так, чтобы запись v_ij обозначала вершину номер j из подмножества V'_i. Очевидно, что v_0,1 = a, v_k,1 = b. Обозначим через j(v_ij) вес вершины v_ij. Каждой вершине из подмножеств V'₀, V'₁,..., V'_k присвоим вес в соответствии со следующим правилом.

1. Положим j(v_0,1) = 1.

2. , i = 0, 1,..., k-1.

Суммирование необходимо выполнять по всем значениям m, удовлетворяющих условию:

<v_i,m, v_{i+1, j}> Î X.

Пункт 2 означает, что вес вершины v_{i+1, j} определяется как сумма индексов всех тех вершин из множества V'_i, которые являются начальными по отношению к вершине v_{i+1, j}.

При выполнении п.2 следует соблюдать очередность: вначале определяются веса всех вершин из множества V'_i, затем веса всех вершин из следующего за ним множества V'_i+1.

После завершения процедуры вес конечной вершины j(v_k,1) = j(b) будет равен искомому количеству кратчайших путей.

Задача 4°

Алгоритм решения этой задачи вытекает из свойства 3 волнового процесса 2.

Дата добавления: 2015-09-27 | Просмотры: 484 | Нарушение авторских прав