Dijkstra

Der Dijkstra-Algorithmus kann als Verfeinerung der Breitensuche angeschaut werden. Wir müssen die folgenden Punkte umsetzen:

1. Wir nehmen nicht einfach den ersten Knoten auf der Open-List, sondern den Knoten mit der kürzeren Distanz zum Startknoten
2. Für jeden Peer müssen wir den Weg zum Startknoten berechnen.
3. Ev. gibt es bereits einen Weg zum Peer. Dann müssen wir überprüfen, ob der neue Weg besser ist.
4. Abbrechen dürfen wir erst, wenn wir sicher sind, dass es keinen schnelleren Weg zum Zielknoten gibt. Dies ist dann der Fall, wenn der nächst-beste Kandidat auf der openListe der Zielknoten ist.

"""
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