Что такое минимальный путь в графе после алгоритма Дейкстры?

Question

Мой график результатов после применения алгоритма:

введите описание изображения здесь

Что означает вектор P на этом графике? Р = {1, 1, 5, 5, 1}. И что такое короткий путь от вершины 1 до 4?

Answer 1

Вектор P указывает родительский элемент для каждого узла в графе, то есть предыдущее состояние на оптимальном пути от начала до узла.

• Узел 1 является начальным состоянием и имеет 1 (сам) в качестве своего родителя.
• Узел 2 оптимально достигается с 1, поэтому 1 является родительским для 2.
• Узел 3 достигается через путь 1-5-3, поэтому 5 является родительским для 3.
• Узел 4 достигается по пути 1-5-4, поэтому 5 является родительским для 4.
• Узел 5 достигается оптимально с 1, поэтому 1 равно родитель 5.

После родителей, 4 достигается из 5, а 5 достигается из 1.