Графи с дължини на ребрата
До сега ребрата на графите нямаха никаква характеристика — при определяне на дължина на път броехме всяко ребро за единица. Но при моделиране на реални ситуации ребрата невинаги са еднакви: пътищата между населени места имат различна дължина, различно време за преминаване, различна цена (такса).
Затова на всяко ребро присвояваме число — наричаме го тегло или дължина на реброто, а графите — претеглени. Дължината на реброто (u, v) означаваме с c(u, v) — положително число.
Дължина на път и НКП
Дължина на пътя π = u₀, u₁, …, u_k е сумата от дължините на ребрата в него: c(π) = c(u₀,u₁) + c(u₁,u₂) + … + c(u_k−1,u_k). Пътят π е най-къс път (НКП) от u₀ до u_k, ако за всеки друг път π′ между същите върхове е в сила c(π) ≤ c(π′). НКП между два върха винаги е прост път (не повтаря върхове).
Задачи за намиране на НКП
Задачите за най-къс път са едни от най-интересните в алгоритмиката — решенията им пестят време, пари и ресурси. Учебникът посочва три вида:
| Задача | Какво търсим | За кого е интересна |
|---|---|---|
| 1 | НКП от зададен връх u до друг зададен връх v | Всеки, който пътува от едно място до друго |
| 2 | НКП от зададен връх u до всички останали върхове | Търговски пътник, тръгващ от своето населено място |
| 3 | НКП от всеки връх до всеки друг връх | Транспортна фирма, таксита в голям град |
Трите задачи са еквивалентни: решение на задача 2 дава решение на задача 1 (вземаме само пътя до v) и на задача 3 (пускаме я от всеки връх).
Дърво на най-късите пътища (ДНКП)
За всеки свързан граф G и начален връх u може да се построи дърво T с корен u, такова че единственият път в дървото от корена до кой да е връх v е най-къс път от u до v в графа. Това дърво наричаме дърво на най-късите пътища (ДНКП). Построяването му решава задача 2. Всяко ДНКП е покриващо дърво на графа — връзка с предишните два урока!
НКП в непретеглен граф — BFS
Непретегленият граф е претеглен с c(e) = 1 за всички ребра. Тогава дължината на пътя е просто броят на ребрата в него — и решението вече го знаем от урока за обхождане:
Теорема
Нека T е покриващо дърво на свързан граф G с корен r, построено с обхождане в ширина (BFS). Тогава всеки път в T от корена до друг връх е най-къс път в G. Нещо повече — всеки връх от ниво L_i на обхождането е на разстояние точно i от корена.
DFS не върши работа!
С обхождане в дълбочина не може да се намират най-къси пътища. Спомни си дървото от предишния урок, построено в дълбочина — то беше „дълго и тънко" и пътищата в него до корена са далеч от най-къси.
Възстановяване на пътя
НКП от корена до връх v строим отзад напред: започваме от v, продължаваме с родителя му parent(v) в ДНКП, после с родителя на родителя и т.н., докато стигнем корена. Накрая обръщаме реда.
НКП в претеглен граф — алгоритъм на Дейкстра
За претеглен граф с положителни дължини задачата решава класическият алгоритъм на Дейкстра (Dijkstra). Той поддържа множество U от върхове, за които най-късият път вече е окончателно намерен, и за всички останали — временно най-къс път, който минава само през върхове от U.
За всеки връх v пазим две стойности: dist(v) — дължината на временно най-късия път от началния връх, и parent(v) — родителя на v в строящото се дърво.
Стъпките на алгоритъма (по учебника)
- 1. Инициализация: dist(v₀) = 0, parent(v₀) = 0, U = {v₀}; за всеки друг връх i: dist(i) = c(v₀, i), parent(i) = v₀. (Ако няма ребро — c = ∞.)
- 2. Повтаряме n − 2 пъти:
- 2а) Избираме връх j ∉ U с минимално dist(j) и го добавяме в U — неговият път вече е окончателен.
- 2б) За всеки връх k ∉ U пресмятаме dist(k) =
min{dist(k), dist(j) + c(j, k)}— по-добрата от старата стойност и новия път през j. Ако новият е по-къс, parent(k) = j. Тази стъпка се нарича релаксационна.
Лаком (greedy) алгоритъм
Дейкстра на всяка стъпка прави локално най-добрия избор — взима върха с минимална временна дистанция и повече не се връща към него. Такива алгоритми наричаме лакоми. Те невинаги дават оптимално решение, но при Дейкстра (с положителни дължини!) лакомията работи идеално — доказва се в съответната теорема за оптималност.
Трасиране стъпка по стъпка (за дъската)
Прилагаме Дейкстра върху графа от Фиг. 1 с начален връх 1. Проследяваме как се променят dist() на върховете извън U („—" значи, че върхът вече е в U и стойността му е окончателна):
| Стъпка | U | d(2) | d(3) | d(4) | d(5) | d(6) | Избираме |
|---|---|---|---|---|---|---|---|
| старт | {1} | 2 | 4 | ∞ | ∞ | ∞ | 2 (мин.) |
| 1 | {1,2} | — | 3 ←(2+1) | 9 ←(2+7) | ∞ | ∞ | 3 (мин.) |
| 2 | {1,2,3} | — | — | 9 | 6 ←(3+3) | ∞ | 5 (мин.) |
| 3 | {1,2,3,5} | — | — | 8 ←(6+2)! | — | 11 ←(6+5) | 4 (мин.) |
| 4 | {1,2,3,5,4} | — | — | — | — | 9 ←(8+1) | край |
Виж стъпка 3: пътят до връх 4 е бил 9 (през връх 2), но през връх 5 намираме по-къс — 8. Релаксацията го „пренастройва" и parent(4) става 5. Окончателно: d = (0, 2, 3, 8, 6, 9).
Реализация — кодът от учебника
Понятието „безкрайност" няма място в програма — вместо него използваме голямо число M, по-голямо от дължината на кой да е прост път (напр. сумата на всички дължини + 1). Графът представяме с претеглена матрица на съседство: 0 по диагонала, дължината при ребро, INF иначе.
const int INF = 1000000;
static void Dijkstra(int n, int[,] G, int[] d, int[] p, int r)
{ int i, j, minv, mind;
bool[] u = new bool[n + 1];
for (i = 1; i <= n; i++)
{ u[i] = false; p[i] = r; d[i] = G[r, i]; }
p[r] = 0; u[r] = true; d[r] = 0;
for (i = 1; i <= n - 2; i++)
{ minv = 0; mind = INF;
for (j = 1; j <= n; j++)
{ if (u[j] == false && mind > d[j])
{ mind = d[j]; minv = j; }
}
u[minv] = true;
for (j = 1; j <= n; j++)
{ if (d[j] > d[minv] + G[minv, j])
{ d[j] = d[minv] + G[minv, j]; p[j] = minv; }
}
}
}- Първият цикъл е инициализацията: всички са „листа" с родител r и dist = дължината на прякото ребро.
- Вторият (n − 2 повторения): намираме минималния необходен връх
minv, обявяваме го за окончателен, после релаксираме всички през него. - Сложността е O(n²) — за всяко от n повторения обхождаме всички върхове.
Най-къс път от всеки до всеки връх — Флойд–Уоршъл
Задача 3 може да се реши с n изпълнения на Дейкстра. Но има и изумително прост за написване алгоритъм с три вложени цикъла — алгоритъмът на Флойд–Уоршъл. Графът се представя с претеглена матрица на съседство Graph[,]:
static void AllToAll(int n, int[,] Graph)
{ for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (Graph[i, k] + Graph[k, j] < Graph[i, j])
Graph[i, j] = Graph[i, k] + Graph[k, j];
}Идеята: за всеки „междинен" връх k проверяваме дали пътят i → k → j е по-къс от запомнения i → j. След края на работата в реда i и стълба j на матрицата стои дължината на НКП от връх i до връх j.
| Дейкстра | Флойд–Уоршъл | |
|---|---|---|
| Каква задача решава | От един връх до всички (задача 2) | От всеки до всеки (задача 3) |
| Сложност | O(n²) за един начален връх | O(n³) за всички двойки наведнъж |
| Код | ≈ 20 реда | 5 реда (три вложени цикъла) |
| Изискване | Положителни дължини | Без отрицателни цикли |
Какво трябва да запомниш
- Претеглен граф — ребрата имат дължини (тегла); дължина на път = сума от дължините на ребрата му.
- Трите задачи за НКП (до един, до всички, всеки-до-всеки) са еквивалентни; решават се чрез ДНКП.
- Непретеглен граф → BFS дава най-къси пътища (нивото = разстоянието). DFS — не!
- Претеглен граф → Дейкстра: избирай минималния необходен връх + релаксация dist(k) = min{dist(k), dist(j)+c(j,k)}. Лаком алгоритъм, изисква положителни дължини.
- Всеки-до-всеки → Флойд–Уоршъл: три вложени цикъла по междинен връх k.
- Пътя възстановяваме по родителите отзад напред, после обръщаме.