# Graphenalgorithmen
Teil des [[talit:start|Talit Programmierkurses]].
{{:talit:shortest_path_to_ksr.png?nolink&600|}}
Was ist der schnellste Weg von der KSR an den Bahnhof Romanshorn? Von [[https://www.google.com/maps/dir/romanshorn/Rom,+Italien/@44.7122916,8.6925082,7z/data=!3m1!4b1!4m14!4m13!1m5!1m1!1s0x479afd68a90ad591:0x1f84d64ed67113b9!2m2!1d9.3771959!2d47.5657078!1m5!1m1!1s0x132f6196f9928ebb:0xb90f770693656e38!2m2!1d12.4963655!2d41.9027835!3e2/|Romanshorn nach Rom]]? Wie kann ein Staubsaugroboter auf dem kürzesten Weg die ganze Wohnung staubsaugen?
Wie können wir die Probleme überhaupt mathematisch formulieren, so dass wir sie mit einem Algorithmus lösen können?
## Graphen
Alle diese Probleme lassen sich mit mit Graphen formulieren und mit Graphenalgorithmen lösen. Graphen sind eine wichtige Datenstruktur in der Informatik. In der Talit kümmern wir uns erst einmal darum, wie wir einen Graph effizient beschreiben können; anschliessend schreiben wir Code, um verschiedene Eigenschaften von Graphen zu untersuchen - und vielleicht schneller nach Rom zu gelangen.
### Graphen repräsentieren
Wie könnten wir das Weg-Problem (von der KSR an den Bahnhof) abstrakt erfassen? Wir könnten die verschiedenen Wege zum Beispiel so erfassen:
{{:talit:pasted:20220423-154956.png?600}}
Graph mit drei Pfaden zum Bahnhof
Aus was besteht ein Graph? Aus **Knoten** (en. _nodes_ oder _vertices_) und **Kanten** (_edges_). In unserem Fall haben die Kanten **Gewichte**, die die Länge oder Fahrtdauer der einzelnen Strecken repräsentieren.
Wie könnten wir diesen Graphen in Python repräsentieren?
#### Adjazenzmatrix
Einen Graphen mit `m` Knoten speichern wir als `m*m` Matrix. Eine zweidimensionale Matrix ist nichts anderes als eine Liste von Listen gleicher Länge. In jedem Feld speichern wir `True`, wenn eine Verbindung zwischen den zwei Knoten besteht, sonst `False`.
graph = [
# KSR, Sek, Bahnhofstr, Hafenstrasse, Zelgstrasse, Bahnhof
[ False, True, False, False, False, False], # KSR
[ True, False, True, True, True, False], # Sek
[ False, True, False, False, False, True], # Bahnhofstrasse
[ False, True, False, False, False, True], # Hafenstrasse
[ False, True, False, False, False, True], # Zelgstrasse
[ False, False, True, True, True, False], # Bahnhof
]
Hat der Graph Gewichte, speichern wir das Gewicht, `-1` falls es keine Verbindung gibt:
graph = [
# KSR, Sek, Bahnhofstr, Hafenstrasse, Zelgstrasse, Bahnhof
[ -1, 1, -1, -1, -1, -1], # KSR
[ 1, -1, 3, 5, 7, -1], # Sek
[ -1, 3, -1, -1, -1, 7], # Bahnhofstrasse
[ -1, 5, -1, -1, -1, 6], # Hafenstrasse
[ -1, 7, -1, -1, -1, 5], # Zelgstrasse
[ -1, -1, 7, 6, 5, -1], # Bahnhof
]
##### Aufgabe 1a
Codiere eine Funktion, die für eine Adjazenzmatrix und zwei Knotenindices zurückgibt, ob es eine direkte Verbindung gibt zwischen den Knoten:
def has_direct_connection(matrix, n1, n2):
pass
++++Hinweis:|
* Zugriff auf eine verschachtelte Liste mit zwei Klammern: `matrix[2][5]`
++++
#### Adjazenzliste
Die Matrix wird ziemlich gross, sie wächst mit dem Quadrat der Anzahl Knoten `m`. Meist existieren aber lange nicht alle möglichen Kanten in einem Graphen, dann ist es viel effizienter, nur die Liste der Kanten abzuspeichern. Das geht am besten mit _Dictionaries_, das sind Listen, die für jeden Eintrag einen Schlüssel (_Key_) haben, dem ein Wert (_Value_) zugeordnet ist.
graph = {
"ksr": {"sek": 1},
"sek": {"bahnhofstr": 3, "hafenstr": 5, "zelgstr": 7},
"bahnhofstr": {"bahnhof": 7},
"hafenstr": {"bahnhof": 6},
"zelgstr": {"bahnhof": 5},
"bahnhof": {},
}
**Achtung:** Die obige Adjazenzliste codiert einen **gerichteten Graphen** - die Kanten zwischen zwei Knoten haben eine Richtung. Besteht eine Kante von A nach B, bedeutet das nicht automatisch, dass auch eine Kante von B nach A verläuft.
##### Aufgabe 1b
Schreibe eine Funktion `has_direction_connection(list, n1, n2)` die für die Adjazenzliste funktioniert.
++++Hinweise:|
* Zugriff auf ein Dictionary mittels Key:
>>> graph["ksr"]
{'sek': 1}
>>> graph["ksr"]["sek"]
1
* Aber auch:
>>> graph["ksr"]["bahnhof"]
Traceback (most recent call last):
File "", line 1, in
KeyError: 'bahnhof'
* Existenztest:
>>> "bahnhof" in graph["ksr"]
False
>>> "sek" in graph["ksr"]
True
++++
### Tiefensuche
Bevor wir den schnellsten Weg an den Bahnhof zu finden versuchen, wären wir schon mal nur froh, überhaupt einen Weg zu finden. Es könnte ja auch sein, dass wir uns in die Turnhalle begeben, von wo kein Weg zum Bahnhof führt. Oder dass wir von der Bahnhofstrasse zurück zur KSR gelangen:
[[http://magjac.com/graphviz-visual-editor/?dot=digraph%20Romanshorn%20%7B%0A%20%20%20%20rankdir%3DTB%3B%0A%09node%20%5Bshape%20%3D%20doublecircle%3B%20width%3D1%5D%3B%20KSR%20Bahnhof%3B%0A%09node%20%5Bshape%20%3D%20circle%3B%20width%3D1%3B%20fixedwidth%3Dtrue%5D%3B%0A%09KSR%20-%3E%20Turnhalle%20%5B%20label%20%3D%201%20%5D%3B%0A%09KSR%20-%3E%20Weitenzelgstr%20%5B%20label%20%3D%201%20%5D%3B%0A%09Weitenzelgstr%20-%3E%20Bahnhofstr%20%5B%20label%20%3D%208%20%5D%3B%0A%09KSR%20-%3E%20Sek%20%5B%20label%20%3D%202%20%5D%3B%0A%09Sek%20-%3E%20Bahnhofstr%20%5B%20label%20%3D%203%20%5D%3B%0A%09Bahnhofstr%20-%3E%20Bahnhof%20%5B%20label%20%3D%207%20%5D%3B%0A%09Bahnhofstr%20-%3E%20KSR%20%5B%20label%20%3D%204%20%5D%3B%0A%09Sek%20-%3E%20Hafenstrasse%20%5B%20label%20%3D%205%20%5D%3B%0A%09Hafenstrasse%20-%3E%20Bahnhof%20%5B%20label%20%3D%204%20%5D%3B%0A%09Sek%20-%3E%20Zelgstrasse%20%5B%20label%20%3D%207%20%5D%3B%0A%09Zelgstrasse%20-%3E%20Bahnhof%20%5B%20label%20%3D%205%20%5D%3B%0A%7D%0A|{{:talit:pasted:20220521-145117.png?400|Graph}}]]
Detaillierter Graph von der KSR zum Bahnhof
#### Aufgabe 2
* Codiere obigen Graphen als Adjazenzliste in Python.
* Überlege dir, wie du einen möglichen Pfad generieren kannst, der vom ersten zum letzten Knoten führt. Der Pfad soll als Liste von Knotennamen dargestellt werden - z.B. `["KSR", "Sek", "Bahnhofstr", "Bahnhof"]`.
++++Hinweise:|
* Python
* Schleife über ein Dictionary: `for k,v in graph.items():`
* Schleife nur über die Keys: `for k in graph: print(graph[k])`
* Die Funktion könnte beispielsweise `def find_path(graph, node, end)` heissen.
* Algorithmus:
* Wie würdest du in einem Labyrinth vorgehen?
* Was ist die Lösung, falls `node == end`?
* Hm, damit hätten wir ja schon mal einen Anfang...
* ... andernfalls, wenn es einen Pfad von einem Nachbarknoten `neighbor` zu `end` gäbe, was wäre der Pfad von `node` zu `end`?
* Wie kannst du dir merken, ob du bereits in einem Raum warst?
++++
++++Lösung:|
Untenstehender Code nutzt [[wpde>Rekursion]], um das Problem zu lösen:
* falls `node == end`, so kennen wir eine triviale Lösung, nämlich den Pfad `[node]` und wir brechen die Suche ab.
* andernfalls versuchen wir, von jedem Nachbarknoten `neighbor` einen Pfad nach `end` zu finden
* für die Suche von den Nachbarn rufen wir **rekursiv** die gleiche Funktion wieder auf.
* finden wir einen Pfad `path` von `neighbor` nach `end`, so ist der Pfad `[node] + path` eine Lösung für den jetzigen Aufruf.
* gibt es von keinem Nachbarknoten einen Pfad nach `end`, so gibt es auch von `node` her keine und wir geben `False` zurück.
Entscheidend für den Erfolg ist die Vermeidung von unendlicher Rekursion. Wir stellen dies mit zwei Dingen sicher:
- das Problem wird mit jedem Schritt kleiner (gibt es eine Lösung, so ist der Nachbarknoten einen Schritt näher am Ziel als `node`).
- um zu Vermeiden, dass wir einem Zyklus im Graphen folgen, merken wir uns alle besuchten Knoten im Set `visited`. Falls `node` bereits besucht worden ist, haben wir einen Zyklus gefunden und brechen die Suche ab. Die Funktion kann für einen Graphen mit `n` Knoten also höchstens `n` Mal rekursiv aufgerufen werden.
graph = {
"ksr": {"turnhalle" : 1, "sek": 2, "weitenzelgstr": 1},
"turnhalle": {},
"weitenzelgstr" : {"bahnhofstr" : 8},
"sek": {"bahnhofstr": 3, "hafenstr": 5, "zelgstr": 7},
"bahnhofstr": {"bahnhof": 7, "ksr": 4},
"hafenstr": {"bahnhof": 4},
"zelgstr": {"bahnhof": 5},
"bahnhof": {},
}
def find_path(graph, node=None, end=None, visited=None):
"""Returns the list of adjacent nodes from 'node' to 'end' if it exists,
returns False otherwise.
If node is None, the first node in graph is chosen.
If end if None, the last node in graph is chosen.
"""
# Choose first and last nodes in graph if not given.
if node == None:
node = next(iter(graph))
if end == None:
end = list(graph)[-1]
if visited == None:
visited = set()
# If node has already been visited, we closed a cycle - return false.
if node in visited:
return False
# Local check: if node and end are the same, we have a trivial solution.
if node == end:
return [end]
# Record the current node as visited so that we break cycles should we return to it
# in the recursion.
visited.add(node)
# Recursion: If we find a path p from any of our neighbors to end, there is
# a path from 'node' to end that consists of [node] + p.
edges = graph[node]
for neighbor in edges:
path = find_path(graph, neighbor, end, visited)
if path:
# We have found a path from neighbor to end
# -> the path from node to end is the same path, with node prepended.
return [node] + path
# None of our neighbors has a path to 'end' -> give up.
return False
print(find_path(graph))
++++
Obiger Algorithmus heisst Tiefensuche (*Depth First Search* - DFS): Wenn wir an einen neuen Knoten gelangen, suchen wir bei jedem Nachbar-Knoten bis wir entweder eine Lösung gefunden haben oder gescheitert sind. Erst dann besuchen wir den nächsten Nachbar.
### Zyklen finden
Tiefensuche können wir auch verwenden, um Zyklen zu finden. Ein Zyklus ist ein Pfad, bei dem vom letzten Knoten wieder der erste erreichbar ist.
#### Aufgabe 3a
Schreibe Python-Code, der herausfindet, ob ein Graph _zyklenfrei_ ist. D.h. der Code versucht einen Zyklus zu finden und gibt `False` genau dann zurück, wenn er mindestens einen findet.
#### Aufgabe 3b
Schreibe rekursiven Python-Code, der alle Zyklen in einem Graphen findet.
* Funktioniert der Code auch, wenn sich die Zyklen überschneiden?
++++Lösung:|
def find_cycles(graph):
# Record visited nodes in a set, which gives us constant-time lookup of
# nodes.
visited = set()
cycles = []
for node in graph:
if node in visited:
continue # already been here
find_cycles_from_node(graph, node, visited, cycles, [])
return cycles
def find_cycles_from_node(graph, node, visited, cycles, path):
if node in path:
# We have found a cycle from the first occurrence of node
# to here.
# Remove prefix up to the first occurrence:
index = path.index(node)
cycle = path[index:]
cycles.append(cycle)
return
visited.add(node)
path.append(node)
length = len(path)
for neighbor in graph[node]:
# Find cycles forward in graph.
find_cycles_from_node(graph, neighbor, visited, cycles, path)
# Crop path to prefix up to current node.
path = path[:length]
++++
#### Aufgabe 4 - Graph Walk
Wir haben die Tiefensuche nun auf verschiedene Probleme angewendet. Im Allgemeinen haben wir eine Traversierung implementiert, die einen Graphen *linearisiert*, das heisst, jeden Knoten in einer bestimmten Reihenfolge genau einmal besucht.
**Aufgabe**: Schreibe eine Funktion `dfs(graph)`, die die Knoten eines Graphen mittels Tiefensuche ausgibt.
* Die Ausgabe kann mit `print()` erfolgen oder eine Liste zurückgeben.
* Herausforderung: schreibe eine [[talit:generators|Generator-Funktion]] mit dem `yield` Keyword.
++++Lösung:|
Dieser Code gibt die Liste aller Knoten des Graphs aus, wie sie bei einem Tree-Walk in depth-first Reihenfolge zum ersten Mal vorkommen würden.
def traversierung_dfs(graph, node, sequence=None):
sequence = sequence or []
if node in sequence:
return
sequence.append(node)
for neighbor in graph[node]:
traversierung_dfs(graph, neighbor, sequence)
return sequence
print("dfs:", traversierung_dfs(graph, "ksr"))
Untenstehender Code macht dasselbe als *Generator*. Ein Generator ist eine Funktion, die eine Sequenz generiert, aber ohne bereits beim ersten Aufruf die ganze Liste zu berechnen. Stattdessen berechnet der Generator nur das nächste Element und gibt es mit `yield` zurück; dabei wird der Zustand der Funktion automatisch gespeichert, so dass die Ausführung an derselben Stelle wieder aufgenommen wird, an der das letzte Mal `yield` aufgerufen wurde. Eine Funktion, die das `yield` Keyword verwendet, wird automatisch zum Generator.
Mit `yield from ` wird ein anderer Generator `other` in die Sequenz des aufrufenden Generators eingebaut.
Vorteil: Bei einem sehr grossen Graphen muss nicht der ganze Graph abgearbeitet werden, um erste Resultate liefern zu können. Werden nur die ersten paar Elemente benötigt, ist der Aufruf viel schneller.
def dfs(graph, node, visited=None):
""" A generator of all nodes in graph, in depth-first order. """
visited = visited or set()
if node in visited:
return
yield node
visited.add(node)
for neighbor in graph[node]:
yield from dfs(graph, neighbor, visited)
for node in dfs(graph, "ksr"): print(node)
++++
### Breitensuche
Mit der Tiefensuche finden wir Pfade von A nach B in einem Graphen, aber vielleicht nehmen wir dabei grosse Umwege in Kauf, weil wir zuerst weit von A entfernte Knoten besuchen, bevor wir alle Nachbarn von A untersuchen. Wir möchten aber eine Möglichkeit haben, den Graphen *der Nähe nach* zu besuchen, also die Knoten in aufsteigender Distanz von A zu besuchen. Dieses Verfahren heisst **Breitensuche** (*Breadth First Search* - BFS).
#### Aufgabe 5
Überlege dir, wie du vorgehen könntest, um zuerst die unmittelbaren Knoten des Starts zu besuchen, und nur allmählich weitere Kanten zu traversieren. Ignoriere die Kantengewichte dabei erst mal - du kannst von einem ungewichteten Graphen ausgehen.
**Hinweise:**
* Breitensuche lässt sich nicht (einfach) mit Rekursion lösen.
* YouTube Visualisierung[[https://www.youtube.com/watch?v=x-VTfcmrLEQ|BFS]] vs. [[https://www.youtube.com/watch?v=NUgMa5coCoE|DFS]]
* Ordne den Graphen in Schichten nach aufsteigender Distanz (Anzahl Knoten) vom Start.
* Wir möchten zuerst alle Knoten einer Schicht besuchen, bevor wir uns die nächste Schicht vornehmen:
- Zuerst die KSR
- Dann die Turnhalle, Weitenzelgstrasse und die Sek
- Dann die Bahnhofstrasse, Zelgstrasse, Hafenstrasse
- Schlussendlich den Bahnhof
* Wir teilen die Knoten in drei Bereiche:
* Bereits besuchte Knoten, am effizientesten in einem Set: `visited = set()`.
* Entdeckte, aber noch nicht besuchte Knoten in einer Liste: `candidates = [start]`
* Noch unbekannte Knoten (brauchen wir uns nicht zu merken).
* Solange `candidates` nicht leer ist, wird der vorderste Knoten `node` in `candidates` entfernt.
* Falls `node` bereits in `visited` ist, gehen wir zum nächsten (er wurde mehrfach entdeckt über verschiedene Pfade).
* Andernfalls: wird `node` zu `visited` hinzugefügt.
* Falls `node == end` sind wir fertig.
* Alle Nachbarknoten von `node`, die noch nicht in `visited` sind, werden hinten in die `candidates` eingereiht.
++++Lösung:|
def traversierung_bfs(graph, start):
"""Returns the list of nodes in graph reachable from start, in breadth-first order."""
sequence=[] # list of nodes in breadth-first order
candidates = [start] # known nodes we should process
while candidates:
# Handle the next candidate:
# - remove from list
# - if not visited yet: add to sequence and add its neighbors
node = candidates.pop(0)
if node in sequence:
continue
sequence.append(node)
for neighbor in graph[node]:
candidates.append(neighbor)
return sequence
print("bfs: ", traversierung_bfs(graph, "ksr"))
Oder als *Generator*:
def bfs(graph, start):
""" A generator of all nodes in graph, in breadth-first order. """
candidates = [start]
visited = set()
while candidates:
next = candidates.pop(0)
if next in visited:
continue
visited.add(next)
yield next
candidates.extend(graph[next])
++++
#### Aufgabe 6: Pfadsuche mit BFS
Implementiere die Pfadsuche auch mit BFS. Wie zeichnen sich die gefundenen Pfade aus?
++++Hinweise:|
* keine Rekursion!
* Wir merken uns die noch zu besuchenden Knoten in einer FIFO-Liste (first-in, first-out):
* hinten fügen wir neue Kandidaten hinzu (`append`)
* vorne nehmen wir jeweils den nächsten Knoten weg (`pop(0)`)
* Zusätzlich merken wir uns:
* alle besuchten Knoten (`visited`)
* Statt einem Set verwenden wir ein Dictionary für `visited`:
* Wir merken uns für jeden Knoten dessen ersten Vorgängerknoten, um daraus am Schluss den Pfad zu bauen.
++++
++++Lösung:|
def build_path_from_parents(graph, parents, start, end):
"""Builds the path from start to end given a parent dictionary
for all nodes. Also computes the total path length from
the graph adjacency list."""
path = []
node = end
total = 0
while node != start:
parent = parents[node]
edge = graph[parent][node]
total += edge
path.insert(0, (node, edge))
node = parent
path.insert(0, (start, '0'))
result = {
'path': path,
'length': total
}
return result
def find_path_bfs(graph, start, end):
"""Finds a path from start to end using BFS. """
candidates = [start]
visited = {start: None}
while candidates:
next = candidates.pop(0)
for neighbor in graph[next]:
if neighbor not in visited:
visited[neighbor] = next
candidates.append(neighbor)
if neighbor == end:
return build_path_from_parents(graph, visited, start, end)
return None # No path found
++++
### Scale it up - Pfadsuche im öffentlichen Verkehr
Wir wollen unsere Algorithmen an einem etwas grösseren Beispiel testen. Der Schweizer ÖV-Fahrplan listet über 34'000 Haltepunkte auf, und wir wollen Verbindungen zwischen allen möglichen Stationen herausfinden und die Resultate vergleichen.
Der Datenbestand enthält als Adjazenz-Liste alle Haltepunkte, die mit einer Non-Stop-Verbindung zu erreichen sind. Die Nachbarknoten von Romanshorn sind also beispielsweise Amriswil, Egnach und Konstanz, aber nicht Frauenfeld. Zusätzlich enthält die Liste die reine Fahrtdauer in Minuten. Bei Transfer-Verbindungen (Romanshorn - Romanshorn, Bahnhof) ist statt der Fahrzeit die Umsteigezeit angegeben.
>>> import fahrplan
>>> sbb = fahrplan.latest
>>> sbb['Romanshorn']
{'Amriswil': 5, 'Egnach': 1, 'Konstanz': 17, 'Kreuzlingen Hafen': 14, 'Neukirch-Egnach': 2, 'Romanshorn': 3, 'Romanshorn (See)': 5, 'Romanshorn Autoquai': 6, 'Romanshorn, Bahnhof': 3, 'St. Gallen': 18, 'Uttwil': 3, 'Weinfelden': 13, 'Wittenbach': 11}
#### Aufgabe 7: Real-World Beispiel
* Klone das Git Repo https://github.com/tkilla77/ksr_talenta_graphs
* Importiere die Adjacency-List des Schweizer öffentlichen Verkehrs.
* Details im [[https://github.com/tkilla77/ksr_talenta_graphs/blob/main/fahrplan/README.md|README]].
* Teste deine Implementierungen für DFS und BFS
* Finde einen Pfad von Romanshorn nach Lugano
import fahrplan
# Read schedule
sbb = fahrplan.latest
# Find path - depth-first.
# We may need to increase python's recursion depth...
import sys
sys.setrecursionlimit(10000)
dfs_path = find_path_dfs(sbb, "Romanshorn", "Lugano")
# Find path - breadth-first.
bfs_path = find_path_bfs(sbb, "Romanshorn", "Lugano")
##### Fragen
- Hm, der DFS-Pfad scheint nicht wirklich optimal zu sein - weshalb?
- Was hat es mit der Rekursionstiefe auf sich?
- Der BFS-Pfad ist deutlich besser - BFS findet nämlich den Pfad mit den wenigsten Segmenten. Aber ist das bereits der schnellste Pfad?
### Dijkstra - Kürzeste Pfade
In einem ungewichteten Graph finden wir mit der Breitensuche den kürzesten Weg, also den Pfad mit den wenigsten Segmenten. Ist der Pfad aber gewichtet (wie der Haltestellen-Graph mit Minuten-Angaben zu den Reisezeiten), so ist der Weg mit den wenigsten Segmenten nicht unbedingt der schnellste.
Unser Ziel ist es, die Knoten in aufsteigender Distanz von `start` zu besuchen. Wir teilen die Knoten in drei Gruppen:
- die bereits besuchten Knoten
- die entdeckten (aber noch nicht besuchten Knoten): `candidates`
- alle anderen, noch unentdeckten Knoten
Der Algorithmus basiert auf dem folgenden Prinzip:
* Die Kandidaten sind nach aufsteigender Distanz zum Startknoten sortiert.
* Hier liegt der Unterschied zu BFS: statt die neu-entdeckten Kandidaten einfach hinten einzureihen, werden sie nach aufsteigender Distanz zum Start sortiert.
* Für die effiziente Sortierung der Kandidaten benützen wir eine [[wpde>Vorrangwarteschlange|PriorityQueue]].
* Der vorderste Kandidat ist immer der nächste Knoten in aufsteigender Distanz von `start` her.
* Beweis: gäbe es einen Knoten `x` der näher bei `start` liegt, so wäre dessen Vorläufer-Knoten bereits besucht worden und die geringere Distanz von `x` wäre bereits bekannt geworden.
* Achtung: für alle weiteren Kandidaten stimmt die Sortierung noch nicht definitiv: möglicherweise gibt es einen kürzeren Pfad als den bekannten via einen weiter vorne liegenden Kandidaten, dessen Nachbarn noch nicht bekannt sind!
import queue.PriorityQueue
# Create the queue.
candidates = PriorityQueue()
# Add a tuple (distance, node) to the queue.
candidates.put((0, start))
# ...
while candidates:
# Pop the next candidate off the queue - it is the nearest
# of all known candidates.
distance, node = candidates.get()
* Für alle besuchten oder entdeckten Knoten merken wir uns die kürzeste bekannte Distanz von `start` in einem Dictionary `distances`.
* Beim Besuch des vordersten Knotens `node` gehen wir wie folgt vor:
* wenn `node == end`, so haben wir den kürzesten Pfad gefunden.
* alle Nachbarn `neighbor` von `node` werden untersucht:
for neighbor, edge in graph[node].items():
* wir berechnen die Distanz von `start` zu `neighbor` via `node` aus der Distanz von `node` und der Kantenlänge von `node` zu `neighbor`:
new_distance = distance + edge
* in `distances` schauen wir nach, ob der Knoten bereits bekannt ist. Die `get` Funktion eines Dictionary gibt das zweite Argument zurück, wenn der Key nicht gefunden wird - in unserem Fall unendlich (`math.inf`).
old_distance = distances.get(neighbor, inf)
* falls die neue Distanz kürzer ist, merken wir uns die Distanz und fügen den Knoten an der richtigen Stelle in `candidates` ein.
* zusätzlich unterhalten wir wie bei BFS ein Dictionary mit den Elternknoten jedes Knotens, um daraus den Pfad aufzubauen, wenn wir ans Ziel gelangt sind.
Der Aufbau des Pfades mithilfe der Elternknoten erfolgt gleich wie bei BFS.
++++Lösung|
from math import inf
from queue import PriorityQueue
def shortest_path(graph, start, end):
"""Dijkstra shortest path."""
# Candidates to process next, ordered by increasing distance.
# The head of the queue is guaranteed to be the next node to be visited,
# while the order of subsequent nodes could still be reordered if and preceding
# node offers a shorter path to them.
candidates = PriorityQueue()
candidates.put((0, start))
parents = {}
# In addition to BFS, we record for each discovered node the currently known shortest
# distance from start.
distances = {start: 0}
while candidates:
# print(distances)
# print(candidates.queue)
# input()
# Let's visit the closest node not yet visited. The first candidate node is
# guaranteed to be the closest one of the candidates.
distance, node = candidates.get()
if node == end: # We're done.
return build_path_from_parents(graph, parents, start, end)
if distances.get(node, inf) < distance:
continue # Node was already visited. See comment below.
for neighbor, edge in graph[node].items():
new_distance = distance + edge
old_distance = distances.get(neighbor, inf)
if old_distance <= new_distance:
continue # Neighbor already discovered via some shorter path
# Otherwise: we discovered a shorter (or new) path to neighbor - record it
# and add to candidates.
distances[neighbor] = new_distance
# To be correct, we'd need to remove any old record (old_distance, neighbor)
# in the candidates, but that is expensive. Instead, we leave it in and
# rely on the fact that the neighbor will be visited only once through the shortest
# path.
candidates.put((new_distance, neighbor))
parents[neighbor] = node
return None # No path found
++++
### Visualisierung
Mit Folium lassen sich die gefundenen Pfade hübsch visualiseren. Der Code für untenstehende Grafik findet sich auf [[https://github.com/tkilla77/ksr_talenta_graphs/blob/main/sbb.ipynb|github]].
{{:talit:algorithmen:pasted:20250302-193146.png?nolink}}
Pfad von Romanshorn nach Bern --- Rot: BFS, Grün: DFS, Blau: Dijkstra