Ein frei kopier- und anpassbares Lehrmittel von eduskript.org

Built with Eduskript
FĂŒr wen ist das?

Diese Seite ist eine freiwillige Challenge fĂŒr alle, die schneller fertig sind und mehr wollen - sie ist nicht PrĂŒfungsstoff. Wer sie durchspielt, hat am Ende den Dijkstra-Algorithmus aus der Routing-Lektion selbst programmiert und nebenbei Dictionaries gelernt, eine der wichtigsten Datenstrukturen der Informatik.

Wir bleiben beim selben Netz wie in der Routing-Lektion: fĂŒnf Router A bis E, die Zahlen sind die Kosten (z.B. Latenz).

Teil 1 — Der Graph als Liste

Zuerst stellen wir den Graphen als Kantenliste dar: eine Liste von Kanten, jede Kante ist [knoten_a, knoten_b, kosten].

kanten = [["A","B",4], ["A","C",2], ["B","D",3],
          ["C","D",1], ["C","E",5], ["D","E",2]]

Die Kanten sind ungerichtet: ["A","B",4] heisst, man kommt von A nach B und von B nach A, beides fĂŒr Kosten 4.

Stufe 1: Nachbarn finden

Schreiben Sie nachbarn(kanten, k) - die Liste aller [nachbar, kosten] von Knoten k. Denken Sie an beide Richtungen: k kann an erster oder zweiter Stelle einer Kante stehen.

PythonLoading editor

kanten = [["A","B",4], ["A","C",2], ["B","D",3],
          ["C","D",1], ["C","E",5], ["D","E",2]]

def nachbarn(kanten, k):
    ergebnis = []
    for kante in kanten:
        a, b, kosten = kante[0], kante[1], kante[2]
        # Ist k einer der beiden Endpunkte? Dann ist der andere ein Nachbar.
        ...
    return ergebnis

print(nachbarn(kanten, "C"))   # [['A', 2], ['D', 1], ['E', 5]]

Stufe 2: Was kostet das ganze Netz?

Summieren Sie alle Kantengewichte.

PythonLoading editor

kanten = [["A","B",4], ["A","C",2], ["B","D",3],
          ["C","D",1], ["C","E",5], ["D","E",2]]

def netzwerkkosten(kanten):
    # Summe aller Kantengewichte.
    ...

print(netzwerkkosten(kanten))   # 17

Stufe 3: Kosten eines Pfades

Gegeben ein Pfad wie ["A","C","D","E"] - wie teuer ist er? Summieren Sie die Kosten der aufeinanderfolgenden Kanten. Die Hilfsfunktion kante_kosten ist schon da.

PythonLoading editor

kanten = [["A","B",4], ["A","C",2], ["B","D",3],
          ["C","D",1], ["C","E",5], ["D","E",2]]

def kante_kosten(kanten, a, b):
    for kante in kanten:
        if (kante[0] == a and kante[1] == b) or (kante[0] == b and kante[1] == a):
            return kante[2]
    return None

def pfad_kosten(kanten, pfad):
    total = 0
    for i in range(len(pfad) - 1):
        # Addiere die Kosten der Kante zwischen pfad[i] und pfad[i+1].
        ...
    return total

print(pfad_kosten(kanten, ["A","C","D","E"]))   # 5

Stufe 4: Grad eines Knotens

Wie viele Verbindungen hat ein Knoten?

PythonLoading editor

kanten = [["A","B",4], ["A","C",2], ["B","D",3],
          ["C","D",1], ["C","E",5], ["D","E",2]]

def grad(kanten, k):
    # ZĂ€hle die Kanten, an denen k beteiligt ist.
    ...

print(grad(kanten, "C"))   # 3
Ist Ihnen etwas aufgefallen?

In jeder dieser Aufgaben mussten Sie die Kantenliste durchsuchen - immer wieder for kante in kanten. Bei Dijkstra brĂ€uchten wir das in jedem Schritt erneut. Das ist mĂŒhsam und langsam. Es gibt eine Datenstruktur, die genau dieses Problem löst.

Zwischenspiel — Dictionaries

Eine Liste greift ĂŒber die Position zu: liste[0], liste[1]. Bei Graphen ist das unpraktisch - der Knoten heisst ja "C", nicht 2.

Ein Dictionary (dict) greift ĂŒber einen SchlĂŒssel zu, z.B. einen Namen. Jeder SchlĂŒssel zeigt auf einen Wert:

PythonLoading editor

alter = {"Anna": 17, "Ben": 16}   # SchlĂŒssel: Wert, SchlĂŒssel: Wert

print(alter["Anna"])     # 17  -> Zugriff ĂŒber den SchlĂŒssel
alter["Carla"] = 18      # neuen Eintrag anlegen
alter["Ben"] = 15        # bestehenden Wert Àndern
print("Ben" in alter)    # True -> gibt es den SchlĂŒssel?

for name in alter:       # eine Schleife lĂ€uft ĂŒber die SchlĂŒssel
    print(name, "ist", alter[name])

Drei Dinge zum Merken:

  • Ein SchlĂŒssel kommt nur einmal vor. Erneutes Zuweisen ĂŒberschreibt den Wert.
  • dict[schluessel] liest, dict[schluessel] = wert schreibt.
  • for k in dict lĂ€uft ĂŒber die SchlĂŒssel.

Teil 2 — Der Graph als Dictionary

Jetzt speichern wir die Nachbarn direkt unter dem Knotennamen. Kein Durchsuchen mehr:

graph = {
    "A": [["B",4], ["C",2]],
    "B": [["A",4], ["D",3]],
    "C": [["A",2], ["D",1], ["E",5]],
    "D": [["B",3], ["C",1], ["E",2]],
    "E": [["C",5], ["D",2]],
}

graph["C"]   # [['A',2],['D',1],['E',5]]  -> sofort da, ohne Suchen

Stufe 5a: Von der Liste zum Dictionary

Bauen Sie aus der Kantenliste das Adjazenz-Dictionary. FĂŒr jede Kante tragen Sie beide Richtungen ein.

PythonLoading editor

kanten = [["A","B",4], ["A","C",2], ["B","D",3],
          ["C","D",1], ["C","E",5], ["D","E",2]]

def kantenliste_zu_graph(kanten):
    graph = {}   # leeres Dictionary
    for kante in kanten:
        a, b, kosten = kante[0], kante[1], kante[2]
        # Lege graph[a] = [] an, falls a noch nicht existiert (Tipp: if a not in graph).
        # HĂ€nge dann [b, kosten] an graph[a] an - und [a, kosten] an graph[b].
        ...
    return graph

print(kantenliste_zu_graph(kanten)["C"])   # [['A', 2], ['D', 1], ['E', 5]]

Stufe 5b: Dijkstra — die kĂŒrzesten Distanzen

Jetzt der Kern. Wir berechnen die kĂŒrzeste Distanz vom Start zu allen Knoten - genau die Tabelle aus der Routing-Lektion. Das GerĂŒst inklusive Min-Scan ist vorgegeben; Sie fĂŒllen nur die zwei Zeilen, die die Nachbar-Distanzen aktualisieren.

PythonLoading editor

graph = {
    "A": [["B",4], ["C",2]],
    "B": [["A",4], ["D",3]],
    "C": [["A",2], ["D",1], ["E",5]],
    "D": [["B",3], ["C",1], ["E",2]],
    "E": [["C",5], ["D",2]],
}

def kuerzeste_distanzen(graph, start):
    unendlich = float("inf")
    distanz = {}
    besucht = {}
    for k in graph:
        distanz[k] = unendlich
        besucht[k] = False
    distanz[start] = 0

    while True:
        # 1) Unbesuchten Knoten mit der kleinsten Distanz suchen (Min-Scan).
        aktuell = None
        kleinste = unendlich
        for k in graph:
            if not besucht[k] and distanz[k] < kleinste:
                kleinste = distanz[k]
                aktuell = k

        if aktuell is None:   # kein erreichbarer Knoten mehr -> fertig
            break

        # 2) Alle Nachbarn prĂŒfen und ggf. eine kĂŒrzere Distanz eintragen.
        for nachbar, kosten in graph[aktuell]:
            neue_distanz = ...                       # Distanz bis aktuell + Kantenkosten
            if neue_distanz < distanz[nachbar]:
                ...                                  # neue, kĂŒrzere Distanz speichern

        besucht[aktuell] = True   # 3) Knoten abhaken

    return distanz

print(kuerzeste_distanzen(graph, "A"))
# {'A': 0, 'B': 4, 'C': 2, 'D': 3, 'E': 5}

Stufe 6: Den Pfad rekonstruieren

Distanzen allein sagen noch nicht, welchen Weg man nimmt. Dazu merken wir uns fĂŒr jeden Knoten den VorgĂ€nger und laufen am Ende vom Ziel rĂŒckwĂ€rts zurĂŒck. Dijkstra ist hier fertig vorgegeben - Sie bauen nur den Pfad am Schluss zusammen.

PythonLoading editor

graph = {
    "A": [["B",4], ["C",2]],
    "B": [["A",4], ["D",3]],
    "C": [["A",2], ["D",1], ["E",5]],
    "D": [["B",3], ["C",1], ["E",2]],
    "E": [["C",5], ["D",2]],
}

# Ein zweites Netz mit sechs Knoten zum Testen:
graph2 = {
    "A": [["C",1], ["B",2]],
    "B": [["A",2], ["D",5]],
    "C": [["A",1], ["E",2]],
    "D": [["B",5], ["F",4], ["E",2]],
    "E": [["C",2], ["F",1], ["D",2]],
    "F": [["E",1], ["D",4]],
}

def kuerzester_pfad(graph, start, ziel):
    unendlich = float("inf")
    distanz, vorgaenger, besucht = {}, {}, {}
    for k in graph:
        distanz[k] = unendlich
        vorgaenger[k] = None
        besucht[k] = False
    distanz[start] = 0

    while True:
        aktuell = None
        kleinste = unendlich
        for k in graph:
            if not besucht[k] and distanz[k] < kleinste:
                kleinste = distanz[k]
                aktuell = k
        if aktuell is None:
            break
        for nachbar, kosten in graph[aktuell]:
            neue_distanz = distanz[aktuell] + kosten
            if neue_distanz < distanz[nachbar]:
                distanz[nachbar] = neue_distanz
                vorgaenger[nachbar] = aktuell   # merke, woher der beste Weg kam
        besucht[aktuell] = True

    # Pfad vom Ziel rĂŒckwĂ€rts ĂŒber die VorgĂ€nger aufbauen:
    pfad = []
    k = ziel
    while k is not None:
        ...                 # k an den Pfad anhÀngen
        k = vorgaenger[k]   # einen Schritt zurĂŒckgehen

    ...                     # den Pfad umdrehen, damit er von start nach ziel zeigt
    return pfad

print(kuerzester_pfad(graph, "A", "E"))    # ['A', 'C', 'D', 'E']
print(kuerzester_pfad(graph2, "A", "F"))   # ['A', 'C', 'E', 'F']
Noch nicht genug? (offen, ohne Auto-Korrektur)
  • Ausfall simulieren: Entfernen Sie aus graph2 die Kante C–E (in beiden Richtungen) und lassen Sie kuerzester_pfad(graph2, "A", "F") nochmals laufen. Welcher Weg wird jetzt gewĂ€hlt? Vergleichen Sie mit Aufgabe 2 der Routing-Lektion.
  • ZusammenhĂ€ngend? Schreiben Sie ist_verbunden(graph), das prĂŒft, ob man von einem Startknoten jeden anderen erreicht (Tipp: Dijkstra laufen lassen und schauen, ob eine Distanz unendlich bleibt).
  • Engster Knoten: Welcher Router hat den höchsten Grad - und was bedeutet sein Ausfall fĂŒrs Netz?