taramath: Kürzeste Wege

Beispiel

Im folgenden Beispiel wird ein gerichteter Graph definiert sowie ein kürzester Weg von Knoten 0 nach Knoten 11 berechnet. Die Gewichtung der Kanten wird dabei aus der jeweiligen Länge der Kanten bestimmt. Anschließend wird das Ergebnis entsprechend graphisch dargestellt.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot"></div>
<script>


function is_in_list (c, C) {
  for (var k = 0; k < C.length; k++) if (C[k] == c) return true;
  return false;
};

function distance (a, b) {
  return Math.sqrt( (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]) );
};

function normalize (v) {
  var h = Math.sqrt(v[0]*v[0] + v[1]*v[1]);
  if (h == 0) return [0, 0];
  return [v[0]/h, v[1]/h];
};

function directed_edge (a, b, c) {
  var h = 2;
  if (distance(a,b) <= h) return false;
  var v = normalize([b[0]-a[0], b[1]-a[1]]);
  Svg.arrow(a[0], a[1], b[0]-h*v[0], b[1]-h*v[1], c);
  return true;
};


var E = [[0,1],[0,2],[2,3],[1,4],[4,3],[4,8],[8,10],[10,11],[8,9],[9,11],[3,7],[3,5],[7,6],[6,9],[6,10],[5,9]];
var L = [[5,15],[11,32],[18,6],[26,18],[27,32],[31,4],[36,15],[39,25],[47,35],[51,11],[60,21],[75,6]];
var w = [];
for (var k = 0; k < E.length; k++) w.push(distance(L[E[k][0]], L[E[k][1]]));

var P = Digraph.shortest_path(E, 0, 11, w);


Svg.init("plot", 480, 240);
Svg.clear("#f8f8f8");
Svg.resize(0, 80, 0, 40);

for (var k = 0; k < E.length; k++) {
  var t = "#cccccc";
  if (is_in_list(k, P.s) == true) t = "#0059c5";
  directed_edge(L[E[k][0]], L[E[k][1]], t);
};

for (var k = 0; k < L.length; k++) {
  var t = "#cccccc";
  if (is_in_list(k, P.p) == true) t = "#0059c5";
  Svg.disc(L[k][0], L[k][1], 1, t, "#f8f8f8");
};

Svg.draw();


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

Vorschau aktualisieren

Kürzeste Wege

in gerichteten Graphen