taralino

.shortest_path

Die Funktion Graph.shortest_path(E, a, b) erwartet folgende (verpflichtende) Argumente:

Argument	Datentyp	Hinweis
E	Datenfeld	Kantenmenge als (m x 2)-Matrix
a	Zahl	Index des Startknotens
b	Zahl	Index des Zielknotens

Es wird der kürzeste Weg von a nach b bestimmt. Zurückgegeben wird ein Objekt bestehend aus folgenden Daten:

Variable	Datentyp	Hinweis
nodes	Datenfeld	Liste der Knoten-Indize, welche den kürzesten Weg bilden
edges	Datenfeld	Liste der Kanten-Indize, welche den kürzesten Weg bilden
distance	Zahl	Länge des kürzesten Weges

Zudem können folgende Optionen verwendet werden:

Variable	Datentyp	Hinweis	Default-Wert
weights	Datenfeld	Gewichte der Kanten als m-Vektor	alle Gewichte gleich 1

Unter Verwendung der Option weights kann eine Gewichtung der Kanten spezifiziert werden.

Hinweis: Falls kein Weg von a nach b existiert, wird eine entsprechende Zeichenkette zurückgegeben.

Beispiel

Es wird ein zufälliger Graph erzeugt. Anschließend wird ein kürzester Weg bestimmt.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

var G = Graph.random(16);
Graph.plot(G.E, {width:240, locations:G.L});

var P = Graph.shortest_path(G.E, 14, 11, {weights:G.w});
Console.print(P.nodes);
Console.print(P.edges);
Console.print(P.distance);

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

Vorschau Download Kopie speichern