Крок 5

(I) Якщо позначка у вершині x має вигляд (+z, m(х)), то змінити потік уздовж дуги (z, x) з c(z, х) на с(z,х)+m(t).

(II) Якщо позначка у вершині x: має вигляд (-х, z), то змінити з c(x, z) на с(х, z)–m(t).

Крок 6. Якщо z=s, то стерти усі позначки і повернутися до кроку 1, щоб почати розставляти позначки, але використовуючи вже покращений потік, знайдений на кроці 5. Якщо z < > s, то х=z i повернути до кроку 5.

Найкоротша відстань між вершинами (алгоритм Дейкстри)

Алгоритм Дейкстри використовується для визначення найкоротшої відстані між двома вершинами.

Позначення:

D[i] – найкоротша у цей момент відстань від вершини поч до вершини і.

flag[i] – інформація про перегляд вершини i: 0 – якщо вершина не переглянута, 1 – якщо переглянута. Якщо вершина переглянута, то для неї D[i] є найкоротшою відстанню від вершини поч до вершини і.

parent[i] – інформація про номер вершини, що передує вершині і у найкоротшому шляху від вершини поч.

minv – це мінімальна відстань.

Наведемо типовий алгоритм роботи:

для і від 1 до N виконувати

предок[і]:=нач;

flag[і]:=0;

D[і]:=С[нач,і];

flag [поч]:=1; {поки ми знаємо тільки відстань}

parent[поч]:=0; {від вершини поч до неї ж, рівне 0}

для і від 1 до N-1 виконувати

minv:=нескінченність;

для j від 1 до N виконувати

якщо (flag [j]=0) і (minv > D[j]) {знаходимо мінімальне}

то minv:=D[j]; {відстань}

k:=j; {до непомічених вершин}

flag[k]:=1; {вершина k позначається переглянутою}

для j від 1 до N виконувати {виконуємо перегляд}

якщо flag[j]=0 і D[j]>D[k]+С[k,j]

{якщо для вершини j ще не знайдена найкоротша відстань від поч,

і з вершини j по дузі С[k,j] шлях у j коротший,

ніж знайдений раніше}

то D[і]:=D[k]+С[k,j] {то запам'ятовуємо його}

parent[j]:=k;

Контрольні запитання:

1. Дайте визначення графу.

2. Який граф називається орієнтованим, неорієнтованим, зваженим, мультиграфом, нуль-графом, простим графом.

3. Що таке орграф та неорграф?

4. Що таке шлях, контур, петля?

5. Що таке ребро, ланцюг, цикл?

6. Поясніть поняття слабкої, сильної та однобічної зв’язності.

7. Що називається деревом, лісом, контуром, редукцією?

8. Як можна здійснити подання графа?

9. Поясніть алгоритм проходження графа вглиб.

10. Поясніть алгоритм проходження графа вшир.

11. Опишіть задачу про максимальний потік, принцип її розв’язування.

12. Опишіть задачу Дейкстри та принцип її розв’язування.