Welchen Algorithmus für den kürzesten Weg sollte ich für ein gewichtetes Stadtstraßennetz in Python verwenden? ⇐ Python

[Anonymous]

Ich arbeite an einem realen Navigationsproblem, bei dem ein städtisches Straßennetz als gewichtetes Diagramm (Entfernungen in Kilometern) dargestellt wird.
Die Aufgabe besteht darin, den kürzesten Weg von Nord-Nazimabad (Start) nach Gulshan Iqbal (Ziel) zu berechnen.
Ich habe das Diagramm mithilfe eines klassenbasierten Ansatzes in Python implementiert, bin mir jedoch nicht sicher, welchen Algorithmus für den kürzesten Weg ich auswählen soll und wie ich seine Verwendung für dieses Szenario rechtfertigen soll.
Hier ist mein aktueller Code (Algorithmus absichtlich noch nicht implementiert):
Klasse CityGraph:

Code: Select all

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

Problemdetails:
Das Diagramm ist mit positiven Kantenkosten (Kilometer) gewichtet.
Single-Source-to-Single-Destination-Problem
(Nord-Nazimabad → Gulshan Iqbal)
Reales Logistik-/Navigationsszenario, bei dem die Minimierung der Entfernung wichtig ist
In Betracht gezogene Algorithmen:
Modell)
Fragen:
F1)Welcher Algorithmus sollte für dieses Problem ausgewählt werden?
F2)Warum eignet sich dieser Algorithmus, um den kürzesten Weg von Nord-Nazimabad nach Gulshan Iqbal in einem gewichteten Straßennetz zu finden?
F3)Wie kann der gewählte Algorithmus sauber in diese bestehende klassenbasierte Struktur integriert werden?