Digraph.shortest_path

zur Berechnung eines kürzesten Weges

q r s u t

Funktionsübersicht

.random .complete .plot .degree .degree_in .degree_out .incidence_matrix .adjacency_matrix .is_simple .is_connected .shortest_path .distance .max_flow

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

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.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot" style="display:inline-block;"></div>
<textarea id="output" style="width:300px; height:150px;"></textarea>
<script>

var E = [[3,4],[1,3],[1,2],[0,1],[2,3]];
var P = Digraph.shortest_path(E, 0, 4);

Digraph.plot("plot", E, "large", 300);

Print.init("output");
Print.set_digits(0);
Print.object("Knoten-Indize:");
Print.object(P.p);
Print.object("Kanten-Indize:");
Print.object(P.s);

</script>
</body>
</html>

Vorschau aktualisieren

Beispiel

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.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot" style="display:inline-block;"></div>
<textarea id="output" style="width:300px; height:150px;"></textarea>
<script>

var G = Digraph.random(12);
var P = Digraph.shortest_path(G.E, 2, 11, G.w);

Digraph.plot("plot", G.E, G.L, "large", 300);

Print.init("output");
Print.set_digits(0);
Print.object("Knoten-Indize:");
Print.object(P.p);

</script>
</body>
</html>

Vorschau aktualisieren

Impressum und Kontakt

Datenschutzerklärung

Rechtliche Hinweise