Рассматриваем всевозможные маршруты из u. Вершины, в которые ведут рёбра из u, называются соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины.
Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
пример поиска кратчайшего пути на графе (алгоритм Дейкстры)
Задача. Для орграфа найти длины кратчайших путей от вершины s ко всем остальным вершинам и восстановить кратчайшие пути к ним.
Задача. Для орграфа найти длины кратчайших путей от вершины s ко всем остальным вершинам и восстановить кратчайшие пути к ним.
Задача. Для н-графа найти длины кратчайших путей от вершины a ко всем остальным вершинам и восстановить кратчайшие пути к ним.
Задача. Для н-графа найти длины кратчайших путей от вершины a ко всем остальным вершинам и восстановить кратчайшие пути к ним.
Задача. Для н-графа найти длины кратчайших путей от вершины a ко всем остальным вершинам и восстановить кратчайшие пути к ним.
Задача. Для н-графа найти длины кратчайших путей от вершины 1 ко всем остальным вершинам и восстановить кратчайшие пути к ним.
Задача. Для н-графа найти длины кратчайших путей от вершины 1 ко всем остальным вершинам и восстановить кратчайшие пути к ним.
