Алгоритъм на Дейкстра
(Dijkstra's algorithm code: c++)

     Съществуват различни алгоритми за намиране на най-къс път в граф. Алгоритъмът на Дейкстра построява дърво на най-късите пътища от начален връх до всички останали върхове в граф, на който теглата на дъгите са неотрицателни числа. За конкретния пример, алгоритъмът строи дървото на най-късите пътища от начален връх v[0] до всички останали върхове в граф G.
  Създаден през 1959 г. от холандския учен Edsger Wybe Dijkstra (роден на 11 май 1930 г. в Rotterdam Netherlands).
   Един от най-ефективните и най-често използвани алгоритми за динамична маршрутизация. Използва се за маршрутизация на така наречения метод: състояние на връзката (link state), когато маршрутизаторите обменят информация само за своите връзки към мрежата с всички маршрутизатори в нея (използва разновидност на алгоритъма на Дейкстра- SFP – Shortest Path First).

     Приемаме,че имаме претеглен граф G=(V,E) V - брой върхове, Е – брой ребра от типа:

graf


   За съхранение на стойностите се използва квадратна матрица на съседство а[N][N]. Ако съществува връзка (ребро) се пише теглото на връзката (разстоянието). Например връзка 1-->2=7 (първи ред, втора колона), 1-->3=9, 1-->6=14, 2-->1=7 (втори ред, първа колона). Ако не съществува ребро се присвоява максимално допустимата стойност за с++ (INT_MAX) или стойност по-голяма от максималното разстояние в матрицата(за примера използвам INF=9999). На главния диагонал се присвояват стойности 0, защото разстоянието от т.1 до т.1, от т. 2 до т.2 е равно на 0.
int a[N][N] = {
          {0, 7, 9, INF, INF,14},
          {7, 0, 10, 15,INF,INF},
          {9, 10, 0,11,INF, 2},
          {INF,15,11,0,6,INF},
          {INF,INF,INF,6,0,9},
          {14,INF,2,INF,9,0}
};

Принцип на действие:
Масивът d[] съхранява най-малкото разстояние, булевия масив v[] - отмята дали даден връх е посетен- true(1) или не (0), първоначално се инициализира с нули. Масива previus[] - съдържа посетените върхове. Обхождането стартира от първия върх и сравнява разстояниятя if (!v[j] && min > d[j]) до съседните не проверени върхове и записваме най-малкото разстояние. Отмятаме възела, като посетен v[k] = true и продължаваме към следващия. По същият начин проверяваме и записваме (сумираме) най-малките разстояния и отмятаме върховете, който вече сме ги посетили (да не ги сумираме повторно). Алгоритъмът се повтаря до достигане на последния връх.
Алгоритъмът е стантдартния, но за отпечатване на пътя (т.е. последователността на посетените върхове) се използва масивът previus[]. Съдържанието на съответния връх (например: previus[5]=3) се използва за индекс (търсим стойността от previus[3]=1) към предходния връх. Отново се използва за индекс (previus[1]). Съответно пътя е 1-3-5.
Тествал съм програмата с няколко рзлични матрици, ето някои от тях:

int a[N][N]= {
          {INF, 1, 4, INF, 2, INF},
          {INF, INF, INF, 9, INF, INF},
          {4, INF, INF, 7, INF, INF},
          {INF, 9, 7, INF, INF, 2},
          {INF, INF, INF, INF, INF, 8},
          {INF, INF, INF, INF, INF, INF}
};


int a[N][N]={
          {INF,5,INF,INF,INF,INF},
          {1,2,3,4,5,6},
          {1,2,3,4,5,6},
          {1,2,3,4,5,6},
          {1,2,3,4,5,6},
          {1,2,3,4,5,6}
};


За тази трябва да промените N от 6 на 7.
#define N 7
int a[N][N]={
          {0, 3, INF, INF,7,INF,INF},
          {3, 0,2,INF,4,3,INF},
          {INF,2,0,2,INF,INF,INF},
          {INF,INF,2,0,INF,INF,2},
          {7,4,INF,INF,0,1,INF},
          {INF,3,INF,INF,1,0,2},
          {INF,INF,INF,2,INF,2,0}
};

За тази трябва да промените N от 6 на 10.
#define N 10
int a[N][N]={
         { 0, 23, INF, INF, INF, INF, INF, 8, INF, INF },
         { INF, 0, INF, 3, INF, INF, 34, INF, INF, INF },
         { INF, INF, 0, INF, INF, INF, INF, 25, INF, INF },
         { INF, INF, 6, 0, INF, INF, INF, INF, INF, INF },
         { INF, INF, INF, INF, 0, 10, INF, INF, INF, INF },
         { INF, INF, INF, INF, 12,0, INF, INF, INF, INF },
         { INF, INF, INF, INF, INF, INF, 0, INF, INF, INF },
         { INF, INF, 25, INF, INF, INF, INF, 0, INF, 30 },
         { INF, INF, INF, INF, INF, INF, INF, INF, 0, INF },
         { INF, INF, INF, INF, INF, INF, INF, INF, INF, 0 },
};

Ако получите разстояние 9999 това означава, че няма път между върховете.


Пример (Dijkstra's algorithm): Извежда най-малките разстояния от връх 1 до всички останали. След това извежда и пътя... .

#include <iostream>// tested on Code::Blocks on Linux
#include <stdio.h>
#include <iomanip>
#include <stdlib.h>
#include <limits.h>
using namespace std;
#define N 6
#define INF 9999
int main()
{
int start = 0,k=0,min,j;
bool v[N]; // visited nodes
int d[N]; // distance
int previus[N]; // previous point
int a[N][N] = {
          {0, 7, 9, INF, INF,14},
          {7, 0, 10, 15,INF,INF},
          {9, 10, 0,11,INF, 2},
          {INF,15,11,0,6,INF},
          {INF,INF,INF,6,0,9},
          {14,INF,2,INF,9,0}
};
// Извеждане на матрицата
for (int i = 0; i< N; i++)
{
for (int j = 0; j< N; j++)
{
cout<< setw(7)<< a[i][j]; }
cout<< endl;
}
// Initialization
for (int i = 0; i < N; i++) {
previus[i] = start;
v[i] = false;
d[i] = a[start][i];
}
v[start] = true;
previus[start] = 0;
d[0] = 0;
for (int i = 0; i < N - 1; i++)
{
min=INF;
for (int j = 0; j < N; j++) {
if (!v[j] && min > d[j]) {
min = d[j];
k = j;
}
}
v[k] = true;
for (int j = 0; j < N; j++)
{
if (!v[j] && d[j] > d[k] + a[k][j])
{
d[j] = d[k] + a[k][j];
previus[j] = k;
}
}
}
cout <<"\n          Width (Разстояние):\n";
for (int i = 0; i< N; i++)
{
cout<< endl;
cout<< 1<< "-->"<< i+1<< "=";
cout<< d[i];
}
cout << "\n          Path (Път):\n";
for (int i = N-1;i > start; i--)
{
cout<< "От "<< i+1<< " до "<< 1<< "-->";
for ( j = i ; j > start;)
{
cout<< j+1<< "-";
j = previus[j];
}
cout<< 1<< endl;
}
return 0;
}




Благодаря за вниманието Ви !