Реалізація алгоритму Дейкстри

У ній використовується масив відстаней та масив позначок. На початку алгоритму відстані заповнюються великим позитивним числом (більшим максимального можливого шляху в графі), а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.

На кожному кроці циклу ми шукаємо вершину з мінімальною відстанню і прапором рівним нулю. Потім ми встановлюємо в ній позначку 1 і перевіряємо всі сусідні з нею вершини. Якщо в ній відстань більша, ніж сума відстані до поточної вершини і довжини ребра, то зменшуємо його. Цикл завершується коли позначки всіх вершин стають рівними 1.

Розглянемо конкретно на прикладі як реалізується цей метод на мові C++.

#include" stdafx. h" .

#include.

usingnamespace std;

constint V = 6;

//алгоритмДейкстры.

void Dijkstra (intGR[V][V], intst).

{.

int distance[V], count, index, i, u, m = st + 1;

bool visited[V];

for (i = 0; i.

{.

distance[i] = INT_MAX; visited[i] = false;

}.

distance[st] = 0;

for (count = 0; count.

{.

int min = INT_MAX;

for (i = 0; i.

if (!visited[i] && distance[i] <= min).

{.

min = distance[i]; index = i;

}.

u = index;

visited[u] = true;

for (i = 0; i.

if (!visited[i] &&GR[u][i] && distance[u] ≠ INT_MAX&&.

distance[u] + GR[u][i].

distance[i] = distance[u] + GR[u][i];

}.

cout <<" Стоимость пути из начальной вершины до остальных: «;

for (i = 0; i.

cout << m < «<< i + 1 <<» = «<< distance[i] << endl;

else cout << m < «<< i + 1 <<» = «<<» маршрутнедоступен" << endl;

}.

//главнаяфункция.

void main ().

{.

setlocale (LC_ALL, «Rus»);

int start, GR[V][V] = {.

{ 0, 1, 4, 0, 2, 0 },.

{ 0, 0, 0, 9, 0, 0 },.

{ 4, 0, 0, 7, 0, 0 },.

{ 0, 9, 7, 0, 0, 2 },.

{ 0, 0, 0, 0, 0, 8 },.

{ 0, 0, 0, 0, 0, 0 } };

cout <> «; cin >> start;

Dijkstra (GR, start — 1);

system («pause>>void»);

}.