Концепции алгоритма Дейкстры и проблемы кодирования - PullRequest
1 голос
/ 10 февраля 2012

Вопрос обновлен

В настоящее время я работаю над реализацией алгоритма Дейкстры в 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

Может ли кто-нибудь помочь мне с переводом этого "псевдокода" в код или даже более значимый псевдокод, было бы здорово, так как я борюсь с этим

1 Ответ

2 голосов
/ 10 февраля 2012

Используйте нативные "python" ссылки между объектами, например:

edges = {1: set([2,3,4]), 2: set([1,5]), ....}
costs = {(1, 2): 99.3, (1, 3): 127.77, ...}

Нет необходимости создавать собственные классы для такой простой задачи.

Следите за вдохновением:

http://python.mirocommunity.org/video/1530/pycon-2010-mastering-team-play

...