taramath
Graph.shortest_path
zur Berechnung eines kürzesten Weges
.random .complete .interval .plot .degree .incidence_matrix .adjacency_matrix .is_simple .is_connected .is_tree .is_chordal .is_bipartite .bipartite .spanning_tree .shortest_path .distance .shortest_path_tree .perfect_elimination .coloring
Beschreibung
Die Funktion besitzt folgende Argumente:
E Kantenmenge als -Matrix
a Index des Startknotens
b Index des Zielknotens
w Gewichtung der Kanten als -Vektor (optional)
Es wird ein kürzester Weg von nach bestimmt. Falls keine Gewichtung der Kanten übergeben wird, werden alle Kantengewichte gleich 1 gesetzt.
Zurückgegeben werden folgende Daten:
p Liste der Knoten-Indize, welche den kürzesten Weg bilden
s Liste der Kanten-Indize, welche den kürzesten Weg bilden
Falls kein Weg von nach existiert, wird ein entsprechender String zurückgegeben.
Beispiel 1
Im folgenden Beispiel wird ein Graph mit 5 Knoten und 5 Kanten erzeugt. Anschließend wird ein kürzester Weg (ohne Gewichtung) zwischen zwei ausgewählten Knoten berechnet und die zugehörigen Knoten- sowie Kanten-Indize ausgegeben. Vorschau aktualisieren
Beispiel 2
Im folgenden Beispiel wird ein zufälliger planarer Graph erzeugt. Anschließend wird ein kürzester Weg zwischen zwei ausgewählten Knoten berechnet und die zugehörigen Knoten-Indize ausgegeben. Vorschau aktualisieren