Головна

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

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

struct edge {

int a, b, cost;

};

int n, m, v;

vector e;

const int INF = 1000000000;

void solve () {

vector d (n, INF);

d [v] = 0;

for (;;) {

bool any = false;

for (int j = 0; j

if (d [e [j] .a]

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

for (int i = 0; i

for (int j = 0; j

if (d [i] [k]

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

BFS

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

Алгоритм працює за  , де  - Число вершин,  - Число ребер.

vector > g; // граф

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

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

queue q;

q.push (s);

vector used (n);

vector 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

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 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

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

}

DFS

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

vector used;

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

 



Олімпіади конкурси | Алгоритм пошуку компонент зв'язності в графі

Пошук точок зчленування | Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі | Розширений Евклід | дискретного логарифмування | Теорема Піка. | Z-функція рядка і її обчислення | Знаходження наідліннейшей зростаючої підпослідовності | Знаходження найбільшою нульовий подматріци | Біноміальні коефіцієнти | числа Каталана |

© um.co.ua - учбові матеріали та реферати