64 Пути в бесконтурном графе.

Общая теория:

У нас есть граф G=(V,E), где связь между вершинами v и w следующая: a(v,w) E. Если связь между вершинами отсутствует, то a(v,w)=.

Если последняя вершина w_o, w₁, …, w_n определяет путь в графе, то его длина равна суммарному весу входящих вершин:

Наша задача – нахождение кратчайшего пути между вершинами S, t. M(S,t) – расстояние между S и t.

Путь из S в t, который имеет минимальную длину – есть кратчайший путь, между вершинами S и t.

d(S,t)=d(S,v_k) + a(v_k,t)

d(S,v_k)=d(S,v_k-1)+a(v_k-1,v_k)

v_k-1 v_k

t

S

Поиск кратчайшего пути в бесконтурном графе:

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

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

Рисунок 3.1. – Заданный граф.

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

Рисунок 3.2 – Матрица смежности.

Для перенумерации графа, так чтобы вершина №1 имела только исходящие ребра, используем алгоритм Topolsoft.

Алгоритм Topolsoft (G,N)

1. for each v ϵ V do p[v] 0

1. for each w ϵ V do

2. for each v ϵ V

3. p[v] p[v]+1

4. end for

5. end for

6. Стек

2. for each v ϵ V do

3. if p[v] = 0 then

4. Стек v

5. end if

6. end for

7. num 0

8. while Стек ≠ do

9. w Стек

10. num num+1

11. N[w] num

12. for each v ϵ V

13. p[v] p[v]-1

14. if p[v] = 0 then Стек v

15. end if

16. end for

17. end while

18. end for

После чего получим следующую нумерацию графа.

Рисунок 3.3. – Переименованный граф.

Алгоритм поиска наикратчайших путей.

После можно найти кратчайшие расстояния от вершины №1 до каждой из вершин по алгоритму DSP.

Алгоритм DSP(G, N, d)

1. for j = 1 to n do d[v_j]

2. d[v₁] 0

3. for j = 2 to n do

4. for I = 1 to j-1 do

5. if d[v_j] d[v_i]+a[v_i, v_j] then

6. d[v_j] d[v_i]+a[v_i, v_j]

7. end if

8. end for

9. end for

10. end for

После выводим на экран результат. При этом вычислительная сложность считаем следующим образом:

И она составит:

65 Алгоритм Флойда поиска кратчайших путей между всеми парами вершин

Общая теория:

У нас есть граф G=(V,E), где связь между вершинами v и w следующая: a(v,w) E. Если связь между вершинами отсутствует, то a(v,w)=.

Если последняя вершина w_o, w₁, …, w_n определяет путь в графе, то его длина равна суммарному весу входящих вершин:

Наша задача – нахождение кратчайшего пути между вершинами S, t. M(S,t) – расстояние между S и t.

Путь из S в t, который имеет минимальную длину – есть кратчайший путь, между вершинами S и t.

d(S,t)=d(S,v_k) + a(v_k,t)

d(S,v_k)=d(S,v_k-1)+a(v_k-1,v_k)

v_k-1 v_k

t

S

Алгоритм Флойда:

# (2)

1 2

(6) (7)

(3)

3 (1) 4

Матрица весов графа:

0 3

А= 2 0

7 0 1

6 0

Матрица расстояний графа:

0 10 3 4

D= 2 0 5 6

7 7 0 1

6 16 9 0

D⁽⁰⁾ =A, D⁽¹⁾, D^(k), D^(k-1), …, D⁽ⁿ⁾=D

Каждая из этих матриц содержит кратчайшие пути с учетом ограничений.

d_ij^(k) – количество промежуточных вершин не > k

d_ij^(k)=min{ d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1)}

Алгоритм Floyd (A[1…n,1…n])

1. D⁰A;

2. for k=1 to n do;

3. for i=1 to n do;

4. for j=1 to n do;

5. if d_ik^(k-1) + d_kj^(k-1)< d_ij^(k-1)then;

6. d_ij^(k) d_ik^(k-1) + d_kj^(k-1);

7. else d_ij^(k) d_ij^(k-1);

8. end for;

9. end for;

10. end for;

11. return T(n).

0 3

D⁽⁰⁾=А= 2 0

7 0 1

6 0

0 3 рассматриваем вершину 1 как промежуточную

D⁽¹⁾= 2 0

7 0 1

6 0

0 3 рассматриваем вершину 1 и 2 как промежуточную

D⁽²⁾= 2 0

7 0 1

6 0

0 3 рассматриваем вершину 1и 2 и 3 как промежуточную

D⁽³⁾= 2 0

7 0 1

6 0

0 3

D⁽⁴⁾= 2 0

7 0 1

6 0

Вычислительная сложность:

O(n³).