Функция кратчайшего пути (алгоритм Дейкстры)

Question

У меня есть фрейм данных, состоящий из широты, долготы, ID узла, от NodeID до Node_ID, длина. Столбцы узлов from и to - это мои ребра. Я могу путешествовать только по краям, когда пытаюсь найти кратчайший путь. Я хочу иметь возможность go от узла к другому узлу, минимизируя при этом общую пройденную длину. Вывод должен возвращать каждый узел, через который я должен пройти, чтобы добраться до пункта назначения. Я перепробовал много встроенных пакетов, таких как cppRouting и igraph, но не могу заставить что-либо работать правильно. Любые идеи о том, как создать функцию или как использовать любые существующие функции для достижения sh этого? Спасибо.

Answer 1

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

Алгоритм:

1) Создать набор sptSet (набор дерева кратчайшего пути), который отслеживает вершины, включенные в дерево кратчайшего пути, т. е. минимальное расстояние от источника которого рассчитывается и завершается. Первоначально этот набор пуст.

2) Присвойте значение расстояния всем вершинам входного графа. Инициализируйте все значения расстояния как БЕСКОНЕЧНЫЙ. Присвойте значение расстояния 0 для исходной вершины, чтобы она выбиралась первой.

3) Хотя sptSet не включает в себя все вершины

… .a) Выберите вершину u, которой нет в sptSet и имеет минимальное значение расстояния.

… .b) Включить u в sptSet.

…. c) Обновить значение расстояния всех смежных вершин u. Чтобы обновить значения расстояния, выполните итерацию по всем смежным вершинам. Если для каждой смежной вершины v сумма значений расстояния u (от источника) и веса края uv меньше значения расстояния v, то обновите значение расстояния v.

Go через следующая ссылка: Печать путей в алгоритме кратчайшего пути Дейкстры