taralino

.shortest_path_tree

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

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

Es wird der kürzeste Wege Baum zum Wurzelknoten a bestimmt. Zurückgegeben wird ein Objekt bestehend aus folgenden Daten:

Variable	Datentyp	Hinweis
E	Datenfeld	Kantenmenge des Baumes als Matrix
w	Datenfeld	Gewichte der Kanten des Baumes als Vektor
distances	Datenfeld	Länge der kürzesten Wege

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 der Graph nicht zusammenhängend ist, so wird die Länge der nicht erreichbaren Knoten auf einen Wert von -1 gesetzt.

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, style:"small"});

var T = Graph.shortest_path_tree(G.E, 14, {weights:G.w});
Graph.plot(T.E, {width:240, locations:G.L, style:"small"});

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

Vorschau Download Kopie speichern