Алгоритмы на графах

1 2 3 4

Байланысты:
Алгоритмы на графах тех прог

Шаг алгоритма

Если все вершины посещены, алгоритм завершается.
В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку.

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

Задача. Для н-графа найти длины кратчайших путей от вершины a ко всем остальным вершинам и восстановить кратчайшие пути к ним.

Задача. Для н-графа найти длины кратчайших путей от вершины a ко всем остальным вершинам и восстановить кратчайшие пути к ним.

Задача. Для н-графа найти длины кратчайших путей от вершины 1 ко всем остальным вершинам и восстановить кратчайшие пути к ним.

d(1,2)=7
d(1,3)=9
d(1,4)=20
d(1,5)=20
d(1,6)=11

Достарыңызбен бөлісу:

1 2 3 4