Вопрос обновлен
В настоящее время я работаю над реализацией алгоритма Дейкстры в Python, я рассмотрел здесь другие вопросы, касающиеся алгоритма, и, похоже, ни один из них не соответствует тому, что я ищу.
В настоящее время моя программа читает два текстовых файла, один из которых содержит диаграмму сетевой маршрутизации network.txt (в основном стоимость маршрута).
0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,0,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0
и тот, который содержит нужный маршрут (route.txt)
B>F
Таблица маршрутизации сети:
(Каждая строка является узлом и его связями, поэтому узел A связан с B, C, D и E)
A B C D E F G
A [0, 2, 4, 1, 6, 0, 0]
B [2, 0, 0, 0, 5, 0, 0]
C [4, 0, 0, 0, 0, 5, 0]
D [1, 0, 0, 0, 1, 1, 0]
E [6, 5, 0, 1, 0, 5, 5]
F [0, 0, 5, 1, 5, 0, 0]
G [0, 0, 0, 0, 5, 0, 0]
Узлы в сети:
([Структура] PreviousNode, DistanceFromSource, посетил)
A [-1, 1000000000, False]
B [-1, 1000000000, False]
C [-1, 1000000000, False]
D [-1, 1000000000, False]
E [-1, 1000000000, False]
F [-1, 1000000000, False]
G [-1, 1000000000, False]
Я вроде понимаю алгоритм Дейкстры, но, используя две имеющиеся у меня структуры данных, в сочетании с необходимостью писать его на Python, я понятия не имею, куда идти отсюда, потому что не могу понять, как это сделать. это не знание языка.
У меня есть какой-то очень простой "псевдокод" для того, что мне нужно сделать дальше
3 - проверить всех не посещенных соседей текущего узла и вычислить
их предварительные расстояния от начального узла, перезаписывая
существующее расстояние, если новое значение меньше
4 - Пометить текущий узел как посещенный (больше не будет проверяться)
5 - Если не существует пункта назначения и существует не посещенный узел, перейдите к невидимому узлу с наименьшим> расстоянием от исходного узла и сделайте его текущим узлом, в противном случае конец
6 - Вернуться к 3
Может ли кто-нибудь помочь мне с переводом этого "псевдокода" в код или даже более значимый псевдокод, было бы здорово, так как я борюсь с этим