Алгоритм Дейкстры (C++)

Алгоритм Дейкстры — алгоритм на графах для нахождения кратчайшего пути от одной из вершин графа до всех остальных.
Описание алгоритма Дейкстры для связного графа.
1. Всем вершинам присваивается вес, равный бесконечности.
2. Выбирается вершина, от которой будут вычисляться пути до остальных вершин графа, эта вершина объявляется текущей, а её вес – равным 0.
3. Вес вершин, соединённых с текущей вершиной ребром, пересчитывается по формуле: вес данной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с данной.
4. В качестве текущей берётся следующая вершина.
5. Пункты 3–4 повторяются до тех пор, пока все вершины не будут рассмотрены.

Было полезно?