кратчайший путь Ява Дейкстры, как выяснить конечный пункт назначения?

Question

Я также пытаюсь изучить графики, используя путь Дейкстры, и использую этот урок для гиков .Я думаю, что понимаю, как это работает, используя вес, чтобы найти кратчайший путь.Однако это может быть глупо, но я не понимаю, как найти пункт назначения, глядя на код.или как 9 входов

Почему 9 входов не могут работать только с тремя?И как программа узнает, где заканчиваться?

Answer 1

Итак, чтобы ответить на первую половину вашего вопроса, нет предопределенного «узла назначения» с алгоритмом Дийсктра, более того, только конечный результат.

В этом примере из кода GeeksforGeeks

void dijkstra(int graph[V][V], int src) 

Мы можем видеть, что алгоритм хочет получить массив всех узлов и с какого узла вы начнете.Каждый узел в этом массиве имеет 9 входов, которые соответствуют заданному расстоянию этого узла от любого другого узла, где значение 0 представляет отсутствие соединения.Например, узел «0» имеет значения:

{0, 4, 0, 0, 0, 0, 0, 8, 0}

Что означаетэтот узел 0 находится в 4 единицах от узла 1, в 8 единицах от узла 7 и либо не имеет связи, либо IS является одним из других 7 узлов.Если у вас есть только 3 узла, то вы будете использовать 3 входа для представления возможных расстояний между всеми 3.

Когда программа исчерпала все возможные узлы и пути, алгоритм остановится.Этот алгоритм ищет минимальное связующее дерево, а не путь из точки А в точку Б.

Answer 2

Программа в этом примере заканчивается, когда все узлы были посещены, она не выбирает конкретное место назначения.Он вычисляет минимальное расстояние (и путь) от узла 0 до каждого узла в графике.

В примере 9 узлов, но, конечно, вы также можете использовать 3 узла или 1000 узлов.