Флойд-Уоршелл

Форд-Беллман

struct edge {

int a, b, cost;

};

int n, m, v;

vector<edge> e;

const int INF = 1000000000;

void solve() {

vector<int> d (n, INF);

d[v] = 0;

for (;;) {

bool any = false;

for (int j=0; j<m; ++j)

if (d[e[j].a] < INF)

if (d[e[j].b] > d[e[j].a] + e[j].cost) {

d[e[j].b] = d[e[j].a] + e[j].cost;

any = true;

}

if (!any) break;

}

// вывод d, например, на экран

}

Флойд-Уоршелл

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

Предполагается, что граф не содержит циклов отрицательного веса (тогда ответа между некоторыми парами вершин может просто не существовать — он будет бесконечно маленьким).

for (int k=0; k<n; ++k)

for (int i=0; i<n; ++i)

for (int j=0; j<n; ++j)

if (d[i][k] < INF && d[k][j] < INF)

d[i][j] = min (d[i][j], d[i][k] + d[k][j]);

BFS

В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе, т.е. путь, содержащий наименьшее число рёбер.

Алгоритм работает за , где — число вершин, — число рёбер.

vector < vector<int> > g; // граф

int n; // число вершин

int s; // стартовая вершина (вершины везде нумеруются с нуля)

queue<int> q;

q.push (s);

vector<bool> used (n);

vector<int> d (n), p (n);

used[s] = true;

p[s] = -1;

while (!q.empty()) {

int v = q.front();

q.pop();

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (!used[to]) {

used[to] = true;

q.push (to);

d[to] = d[v] + 1;

p[to] = v;

}

}

}

Если теперь надо восстановить и вывести кратчайший путь до какой-то вершины , это можно сделать следующим образом:

if (!used[to])

cout << "No path!";

else {

vector<int> path;

for (int v=to; v!=-1; v=p[v])

path.push_back (v);

reverse (path.begin(), path.end());

cout << "Path: ";

for (size_t i=0; i<path.size(); ++i)

cout << path[i] + 1 << " ";

}

DFS

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

vector<bool> used;

void dfs(int v)
{
used[v] = true;
cout << v;
for (vector<int>::iterator i = g[v].begin(); i!= g[v].end(); ++i)
if (!used[*i])
dfs(*i);
}