Digraph.distance

zur Berechnung der Länge 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 die Länge eines kürzesten Weges von nach bestimmt und zurückgegeben. Falls keine Gewichtung der Kanten übergeben wird, werden alle Kantengewichte gleich 1 gesetzt.

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 die Länge eines kürzesten Weges zwischen zwei ausgewählten Knoten berechnet und 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 d = Digraph.distance(E, 0, 4);

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

Print.init("output");
Print.object("Abstand:");
Print.object(d);

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

Vorschau aktualisieren

Beispiel

Im folgenden Beispiel wird ein zufälliger planarer Graph erzeugt. Anschließend wird die Länge eines kürzesten Weges zwischen zwei ausgewählten Knoten berechnet und ausgegeben. Berechnet werden kann dies auch über die Kanten-Indize eines kürzesten Weges.

<!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 d = Digraph.distance(G.E, 2, 11, G.w);

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

var P = Digraph.shortest_path(G.E, 2, 11, G.w);
var h = 0;
for (var k = 0; k < P.s.length; k++) h += G.w[P.s[k]];

Print.init("output");
Print.object("Abstand:");
Print.object(d);
Print.object(h);

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

Vorschau aktualisieren

Impressum und Kontakt

Datenschutzerklärung

Rechtliche Hinweise