Der Dijkstra-Algorithmus kann als Verfeinerung der Breitensuche angeschaut werden. Wir müssen die folgenden Punkte umsetzen:
"""
Name: S. Forster
Datum: 21.2.2019
Beschreibung: Dijkstra
"""
from graph import Graph
def step():
"""
Schrittfunktion: Stellt ein einzelner Suchschritt dar.
Muss beim erzeugen des Graph-Objektes registriert werden.
Wird dann bei jedem Tastendruck aufgerufen.
"""
print(str(graph.openList))
node = graph.openList[0] # bester Knoten suchen auf openlist
for candidate in graph.openList:
if node.g > candidate.g:
node = candidate
if node == graph.targetNode:
graph.running = False
else:
for peer in graph.peers[node]:
if peer not in graph.closedList:
g = node.g + graph.dist[node][peer]
if peer in graph.openList:
if g < peer.g:
peer.parent = node
peer.g = g
else:
graph.openList.append(peer)
peer.parent = node
peer.g = g
graph.closedList.append(node)
graph.openList.remove(node)
graph = Graph(step) # graph erzeugen und Schritt-funktion registrieren
graph.loadGallenbach() # Daten laden. Alternative: graph.loadDeutschland()
#graph.startNode = graph.w # Startknoten vorbereiten
#graph.targetNode = graph.s # Zielknotens vorbereiten
graph.init() # startknoten auf openList
graph.run() # starten