Graph.shortest_path_tree

zur Berechnung eines kürzesten Wege Baumes

q r s u t

Funktionsübersicht

.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 Wurzelknotens
w	Gewichtung der Kanten als -Vektor (optional)

Es wird ein kürzester Wege Baum zur Kantenmenge sowie zum Wurzelknoten bestimmt. Falls keine Gewichtung der Kanten übergeben wird, werden alle Kantengewichte gleich 1 gesetzt.

Zurückgegeben werden folgende Daten:

E	Kantenmenge als Matrix
w	Gewichtung der Kanten als Vektor

Beispiel

Im folgenden Beispiel wird ein zufälliger planarer Graph mit 24 Knoten erzeugt. Anschließend wird der zugehörige minimal spannende Baum sowie der kürzeste Wege Baum zum Wurzelknoten 0 berechnet. Die Ergebnisse werden graphisch dargestellt.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot1" style="display:inline-block;"></div>
<div id="plot2" style="display:inline-block;"></div>
<div id="plot3" style="display:inline-block;"></div>
<script>

var G = Graph.random(24);
var T = Graph.spanning_tree(G.E, G.w);
var S = Graph.shortest_path_tree(G.E, 0, G.w);

Graph.plot("plot1", G.E, G.L, 240);
Graph.plot("plot2", T.E, G.L, 240);
Graph.plot("plot3", S.E, G.L, 240);

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

Vorschau aktualisieren

Impressum und Kontakt

Datenschutzerklärung

Rechtliche Hinweise