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