Граф на плоскости или в пространстве это несколько точек, где некоторые пары точек соединяются линиями. Но не всегда удобно задавать граф в том виде, как это указано в определении. Например, при обработке графа на компьютере, его удобно представлять в виде матрицы (двумерного массива). Разработку программы целесообразно реализовать в среде визуального объектно-ориентированного программирования wxDev-C++.
Опишем пошаговый алгоритм Дейкстры:
В цикле от 1 до N заполнить нулями массив A (инициализация); заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A[i]:=1; C[i]:=0 (i – номер стартовой вершины).
Найти минимум среди неотмеченных (т. е. тех k, для которых A[k]=0); пусть минимум достигается на индексе j, т. е. B[j]B[j]+D[j,k], то (B[k]:=B[j]+D[j,k]; C[k]:=j. Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk.
Теперь надо перечислить вершины, входящие в кратчайший путь. Путь от Vi до Vk выдается в обратном порядке следующей процедурой:
z:=C[k].
Выдать z.
z:=C[z]. Если z = 0, то конец, иначе перейти к 3.2.
Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n2).