Алгоритм Дейкстра

4.якщо c=t, то знайдений шлях довжини d(t), якому можна відновити в такий спосіб: це той шлях між s і t, що складається тільки з позначених на кроці (3) ребер (дуг) (можна довести, що він існує й единий); ВИХІД("рішення знайдене");

5.інакше переходимо на крок (1).

Алгоритм можна модифікувати так, щоб він закінчував роботу після одержання усіма вершинами графа G постійних міток, тобто знаходяться найкоротші шляхи з s в усі вершини графа. Алгоритм визначить основне дерево D найкоротших шляхів з вершини s. Для будь-якої вершини v єдиний (s,v) - шлях у дереві D буде найкоротшим (s,v) - шляхом у графі G.

Алгоритм Дейкстра не завжди знаходить правильне рішення у випадку довільних ваг ребер (дуг) графа. Наприклад, для орграфа, зображеного на малюнку, алгоритм Дейкстра знайде маршрут s(s,t)t довжини 1 між вершинами s і t, а не мінімальний маршрут довжини 2+(-2)=0, що проходить через третю вершину графа.

Приклад орграфа, для якого не будем застосовувати алгоритм Дейкста.

Текст програми написаної на основі алгоритму Дейкстра

/* Алгоритм пошуку дерева найкоротших шляхів у зваженому графі */

/* Е.Дейкстра 1959 р. */

#include

#include

#include

int load_matrix(int n, double* weigh);/* Уведення матриці ваг*/

int deik(int n, int s, double* weigh, int* Q, double* L);/* Алгоритм пошуку*/

void print(int n, int* Q, double* L);/* Висновок результату*/

void main(void){

int n=0,s=0,ret=0;

double *weigh;

int* Q;/* Масив міток покажчиків на попередню вершину*/

double* L;/* Масив найдених ваг шляху до вершини*/

printf("\nАлгоpитм пошуку дерева найкоротших шляхів у зваженому графі.\n");

printf("Е.Дейкстpа, 1959 р.\n");

printf("\nВведіть кількість вершин..");

scanf("%d",&n);