Други алгоритми за најкраток пат во граф
Во претходните предавања, веќе споменавме неколку алгоритми кои може да се користат за откривање на најкраток пат во граф – пред се, тоа беше алгоритамот за пребарување по широчина BFS, кој се користи кога сите ребра во графот имаат иста тежина; и алгоритамот за откривање на најкраток пат во граф Dijkstra, кој се користи кога сакаме да го откриеме најкраткиот пат од едно теме до останатите, а сите ребра во графот имаат ненегативни тежини.
Во продолжение, ќе споменеме два други алгоритми. Првиот, Floyd-Warshall, се користи кога сакаме да го откриеме најкраткиот пат помеѓу сите парови на темиња во графот (а не само од едно теме – извор, како кај Dijkstra). Вториот алгоритам за кој ќе зборуваме (Bellman-Ford) е сличен на алгоритамот Dijkstra, но истиот се користи кога во графот може да постојат и ребра со негативни тежини.
Алгоритам на Floyd-Warshall
Овој алгоритам е толку едноставен за имплементација, што би требало истиот да ви биде прв избор кога имате графови со мал број на темиња (на пример, до 200). Иако истиот користи многу повеќе меморија и има многу поголема временска сложеност од алгоритамот Dijkstra, тоа не претставува никаков проблем кај графови со малку темиња, а фактот што истиот е краток за пишување е голема предност кога сакаме брзо да истражиме информации за некој граф - или да решиме некоја задача поврзана со теоријата на графови за време на натпревар.
Во продолжение, директно ќе пристапиме до преглед на изворниот код на алгоритамот. Сепак, пред тоа, да наведеме дека истиот ќе користи нова матрица dist[i][j], која што ќе ја памети вредноста на најкраткиот пат (во случајот со dist[i][j], помеѓу темињата i и j). На почеток, во истата само ќе ги запишеме тежините на ребрата – т.е. ако постои ребро од темето i до темето j, во dist[i][j] ќе ја запишеме тежината на тоа ребро. Алгоритамот, во продолжение, ќе ги пополни останатите полиња во матрицата, така што по завршувањето на истиот, било која вредност dist[x][y] ќе ја содржи должината на најкраткиот пат од x до y (преку едно или повеќе ребра).
Програма 18.1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_V = 101;
int V;
int dist[MAX_V][MAX_V];
void floyd_warshall()
{
for (int k=0; k<V; k++)
{
for (int i=0; i<V; i++)
{
for (int j=0; j<V; j++)
{
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main()
{
cout << "Number of vertices: " << endl;
cin >> V;
//inicijaliziraj gi vrednostite vo dist
for (int i=0; i<V; i++)
{
for (int j=0; j<V; j++)
{
if (i == j)
{
//rastojanie od teme do samoto sebe e 0
dist[i][i] = 0;
}
else
{
//inaku, pochni so nekoja golema vrednost
//koja oznachuva deka seushte ne sme pronashle pat
dist[i][j] = 1000000000;
}
}
}
int E;
cout << "Number of edges: " << endl;
cin >> E;
cout << "Enter the edges..." << endl;
for (int i=0; i<E; i++)
{
int from, to, weight;
cin >> from >> to >> weight;
dist[from][to] = weight;
//dist[to][from] = weight; (ako grafot e nenasocen)
}
//izvrshi go algoritamot
floyd_warshall();
//neka gi ispechatime site rastojanija
for (int i=0; i<V; i++)
{
for (int j=0; j<V; j++)
{
cout << "dist[" << i << "][" << j << "] = " << dist[i][j] << endl;
}
cout << endl;
}
return 0;
}
Да споменеме неколку работи кои се важни. Најпрвин, забележете дека временската сложеност на овој алгоритам е O(V3), каде V е бројот на темиња (бидејќи имаме три вгнездени for циклуси), со што овој алгоритам е навистина корисен (поради тоа што е едноставен за имплементација) кога во графот има релативно мал број на темиња. Следно нешто на што треба (многу) да внимавате е да ги иницијализирате вредностите во матрицата dist[i][j] како што е тоа направено во програмата. Имено, забележете дека растојанието од едно теме до самото себеси е 0, а дека за останатите вредности во матрицата внесовме голем број (1 000 000 000), кој ни означува дека сеуште немаме откриено пат помеѓу тие две темиња (патот е „бесконечно долг“).
Она на што инсистирам многу да внимавате е како е одбрана самата вредност 1 000 000 000. Имено, бидејќи int може да чува целобројни вредности користејќи 4 бајти меморија, максималниот позитивен број кој може да се запише во него е 231 – 1, што е 2 147 483 647. Бидејќи во алгоритамот имаме собирање на елементи од оваа матрица (dist[i][k] + dist[k][j]), не сакаме збирот на два елементи да ја надмине максималната можна вредност која што може да се запише во променлива од тип int, бидејќи тогаш алгоритамот нема да функционира како што треба. Запаметете - ако на пример поставевме на почетокот dist[i][j] = 2 000 000 000, збирот (dist[i][k] + dist[k][j]) ќе беше број поголем отколку што може да се запише во меморијата за тој податочен тип, и ќе имавме грешки во добиените вредности.
За крај, да забележиме уште нешто. Алгоритамот Floyd-Warshall, за разлика од Dijkstra, може да открива најкраток пат и доколку некои од ребрата имаат тежини кои се негативни броеви – но, НЕ и доколку во графот постои циклус каде што збирот на тежините на ребрата во циклусот е негативен број. Имено, во тој случај, откривањето на најкраток пат нема никаква смисла, бидејќи можеме неограничен број на пати да кружиме во циклусот и да ја намалуваме вредноста на патот до бесконечност (видете ја сликата дадена погоре).
Алгоритам на Bellman-Ford
Во случаи каде што имаме граф и потребно е да најдеме растојание помеѓу две темиња (почеток и крај), или имаме едно почетно теме и сакаме да ги откриеме растојанијата до сите останати темиња во графот, можеме да го искористиме алгоритамот на Bellman-Ford. Според искажаното во претходната реченица, овој алгоритам се користи за решавање на истиот проблем како и алгоритамот Dijkstra, но помеѓу нив постојат и две разлики. Имено, алгоритамот на Bellman-Ford може да се искористи кога во графот постојат ребра со негативни тежини - но, за сметка на ова, истиот работи побавно и има поголема временска сложеност.
Многу почесто (практично кај сите проблеми), имаме графови каде што ребрата имаат тежини кои никогаш не се негативни броеви. Едноставно, кога зборуваме за растојание помеѓу градови, не може да постои растојание кое што е негативен број. Кога зборуваме за потребно време за патување, тогаш повторно, не може да постои време кое што е негативен број, итн. Во сите овие случаи, треба да го користиме алгоритамот Dijkstra, бидејќи истиот функционира многу поефикасно од Bellman-Ford. Само во ситуации каде што имаме еден извор и треба да ги пресметаме растојанијата до останатите темиња, а графот може да содржи и ребра со негативни тежини, треба да го користиме алгоритамот кој ќе го видиме во продолжение.
Инаку, имплементацијата на самиот алгоритам и не е толку сложена. Едноставно, истиот функционира на начин што во неколку итерации (повторувања), истиот ќе ги разгледа сите ребра во графот. Ако во една итерација, при разгледувањето на ребрата се открие пократок пат до некое теме, тогаш алгоритамот ќе продолжи понатаму - со повторно разгледување на сите ребра (во следната итерација), со цел откривање на пократок пат и до некое друго теме. Ова е едноставно за имплементација со помош на неколку for циклуси, како што ќе видиме од следната програма.
Програма 18.2
//koristi C++11 - http://mendo.mk/Lecture.do?id=26
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_V = 101;
int V;
vector<pair<int, int> > G[MAX_V];
vector<int> bellman_ford(int start)
{
vector<int> distances;
distances.resize(V);
for (int i=0; i < V; i++)
{
distances[i] = 1000000000;
}
distances[start] = 0;
for (int iteration=0; iteration <= V + 1; iteration++)
{
bool distances_change = false;
for (int j=0; j<V; j++)
{
for (auto edge : G[j])
{
int from = j;
int to = edge.first;
int weight = edge.second;
if (distances[to] > distances[from] + weight)
{
distances[to] = distances[from] + weight;
distances_change = true;
}
}
}
if (distances_change == false)
{
//nema potreba da prodolzhime, bidejki nemashe
//promena na rastojanijata vo prethodnata iteracija
break;
}
else
{
if (iteration == (V + 1))
{
cout << "Error. Negative-weight cycle." << endl;
}
}
}
return distances;
}
int main()
{
cout << "Number of cities: " << endl;
cin >> V;
int E;
cout << "Number of connections: " << endl;
cin >> E;
cout << "Enter the edges (from, to, weight)..." << endl;
for (int i=0; i<E; i++)
{
int from, to, weight;
cin >> from >> to >> weight;
G[from].push_back({to, weight});
}
int start;
cout << "What's the start city: " << endl;
cin >> start;
vector<int> distances = bellman_ford(start);
for (int i=0; i<V; i++)
{
cout << "distance to city " << i << " is " << distances[i] << endl;
}
return 0;
}
Временската сложеност на овој алгоритам е О(V * E), каде V е бројот на темиња, а E е бројот на ребра. Едноставно, првиот for циклус ќе се изврши нешто повеќе од V пати, а другите два for циклуси служат за разгледување на сите ребра во графот (E) – ги разгледуваме темињата и сите нивни соседи (кои се запишани во низата G[i]). За сите темиња заедно, има вкупно E ребра.
Забележете дека, како и кај алгоритамот на Floyd-Warshall, нема логика да се наоѓа најкраток пат во граф каде што постои циклус и збирот на ребрата во него е негативен (бидејќи тогаш можеме бесконечно пати да се движиме низ него и растојанието континуирано ќе се намалува). Алгоритамот кој го напишавме погоре може да се користи за откривање на такви циклуси, како што е претставено со самиот програмски код. Забележете дека е потребно да се извршат повеќе од V итерации во алгоритамот за да можеме да го откриеме тој факт – ако и после V итерации растојанието помеѓу некои темиња се намалува, тогаш знаеме дека во графот постои проблематичен циклус.
Слично, доколку при одредена итерација и разгледување на сите ребра во графот нема промена на растојанијата, тогаш од алгоритамот можеме да излеземе и порано - како што е имплементирано погоре со наредбата break.
Забележете дека и алгоритамот на Floyd-Warshall може да се искористи за решавање на овој проблем, но тој има временска сложеност O(V3), па внимавајте на бројот на темиња пред да решите да го искористите истиот. Ако можете, направете го тоа, бидејќи тој е полесен за имплементација, а истиот функционира и кога ребрата имаат тежини кои се негативни броеви.
Притоа, при решавањето на проблеми каде што имаме негативни тежини, потребно е да внимаваме и на фактот што кај алгоритмите користевме цел број (1000000000) за означување дека до некое теме не може да се стигне. Но, од гледна точка на алгоритмите, тие го прифаќаат тој број како растојание до темето, па ако има негативно ребро од такво теме до некое друго, тие ќе го искористат истото за намалување на патот до новото теме - па таму ќе има запишано должина од, на пример, 999999980 (иако, можеби, до темето каде што бил запишан бројот 1000000000 не ни може да се стигне - на пример, ако графот е составен од повеќе компоненти). За да знаете дали до овие темиња навистина постои пат, или само било привремено земено некое ребро со негативна тежина, можете да користите некој друг (помал) број за споредба - на пример, ако растојанието е поголемо од 500000000, тогаш може да претпоставиме дека не постои пат, туку само сме искористиле некое ребро од теме до кое воопшто и не може да се стигне (се разбира, кој број ќе го одберете ќе зависи од тоа какви тежини може да имаат ребрата). Вториот начин да се справите со овој проблем е, пред ажурирањето на вредностите во алгоритмите Floyd-Warshall или Bellman-Ford, да проверите дали до соодветното теме постои пат - на пример, пред наредбата (distances[to] = distances[from] + weight), да проверите дали distances[from] е вредност помала од 1000000000. Сепак, негативни тежини се среќаваат ретко во реалноста, па овој дел го наведовме чисто информативно - доколку не ви е јасно зошто алгоритамот открива чудни вредности. Ваква ситуација не може да се случи кога сите ребра имаат тежина која е позитивен број.