Как интегрировать алгоритм Дейкстры во взвешенный граф на основе классов в Python? ⇐ Python

[Anonymous]

Я работаю над реальной навигационной задачей, где сеть городских дорог представлена в виде взвешенного графика (расстояния в километрах).

Цель состоит в том, чтобы вычислить кратчайший путь от Северного Назимабада до Гульшан-Икбала.
У меня есть граф на основе классов структуру, но я не уверен, как правильно структурировать алгоритм Дейкстры внутри этого класса, не допуская смешивания. Я хочу, чтобы код был чистым и модульным.
Вот мой текущий код. Я добавил инициализацию и заполнители, но основная логика Дейкстры еще намеренно не реализована:

Код: Выделить всё

class CityGraph:
def __init__(self):
self.graph = {
"North Nazimabad": {"Saddar": 4, "Bahadurabad": 9, "DHA 6": 7},
"Saddar": {"North Nazimabad": 4, "Bahadurabad": 5, "DHA 6": 10},
"Bahadurabad": {"North Nazimabad": 9, "Saddar": 5, "Sea View": 12},
"DHA 6": {"North Nazimabad": 7, "Saddar": 10, "Clifton": 6},
"Clifton": {"DHA 6": 6, "Sea View": 9, "Boat Basin": 5},
"Boat Basin": {"Clifton": 5, "Tariq Road": 3},
"Sea View": {"Clifton": 9, "Tariq Road": 7, "Bahadurabad": 12},
"Tariq Road": {"Sea View": 7, "Boat Basin": 3, "Gulshan Iqbal": 4},
"Gulshan Iqbal": {"Tariq Road": 4}
}

def shortest_path(self, start, goal):
# initialize distance table
distances = {node: float('inf') for node in self.graph}
previous = {node: None for node in self.graph}
distances[start] = 0
pass

Сведения о проблеме:

• График взвешен с положительными затратами на края
• От одного источника к одному пункту назначения
  
  (Северный Назимабад → Гульшан Икбал)
• Цель — минимизировать общее расстояние (км)

Вопросы:

• Какова правильная структура реализации алгоритма Дейкстры внутри этого метода?
• Какие части алгоритма должны обрабатываться внутри класса, а какие локально в методе?

Мне конкретно нужны руководства по структуре и передовым практикам, а не просто копипаст реализации.

Подробнее здесь: https://stackoverflow.com/questions/798 ... h-in-pytho