Какой алгоритм кратчайшего пути следует использовать для взвешенной городской дорожной сети в Python? ⇐ Python

[Anonymous]

Я работаю над реальной навигационной задачей, где сеть городских дорог представлена в виде взвешенного графа (расстояния в километрах).
Задача состоит в том, чтобы вычислить кратчайший путь от Северного Назимабада (начало) до Гульшан Икбала (пункт назначения).
Я реализовал граф, используя подход на основе классов в Python, но я не понимаю, какой алгоритм кратчайшего пути мне следует выбрать и как оправдать его использование для этого сценария.
Вот мой текущий код (алгоритм еще намеренно не реализован):
класс 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}
}

self.distances = {}
self.previous = {}
self.visited = set()

def shortest_path(self, start, goal):
# Shortest path from "North Nazimabad" to "Gulshan Iqbal"
# Algorithm will be implemented here
pass

Подробности проблемы:
График взвешен с положительными краевыми затратами (километры)
Задача от одного источника до одного пункта назначения
(Северный Назимабад → Гульшан Икбал)
Реальный сценарий логистики/навигации, в котором минимизация расстояния имеет значение
Алгоритмы ниже соображение:
1) Алгоритм Дейкстры
2) Беллмана – Форда
3) Флойда – Уоршалла
4) Поиск A*
5) Равномерный поиск по стоимости (UCS)
6) Жадный поиск лучшего
7) BFS (при преобразовании в невзвешенную модель)
Вопросы:
Q1) Какой алгоритм следует выбрать для этой задачи?
Q2) Почему этот алгоритм подходит для поиска кратчайшего пути от Северного Назимабада до Гульшан-Икбала во взвешенной дорожной сети?
Q3) Как выбранный алгоритм можно четко интегрировать в существующую модель на основе классов? структура?

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