graph/dijkstra_index.html at master · webwriter-app/graph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
<!DOCTYPE html>
<html encoding="utf8">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Testing graph-viz</title>
    <script src="algo_index.ts" type="module"></script>
    <script src="https://cdn.tailwindcss.com"></script>

    <link
      rel="stylesheet"
      href="https://cdn.jsdelivr.net/npm/@shoelace-style/shoelace@2.0.0-beta.85/dist/themes/light.css"
    />
    <script
      type="module"
      src="https://cdn.jsdelivr.net/npm/@shoelace-style/shoelace@2.0.0-beta.85/dist/shoelace.js"
    ></script>
  </head>
  <body>
    <div class="flex justify-center min-h-screen p-10 text-black bg-slate-100 ">
        <div class="flex flex-col max-w-3xl space-y-3">
          <p class="text-3xl">The Dijkstra Algorithm</p>
          <p>
            Der Dijkstra-Algorithmus ist ein Algorithmus zur Bestimmung des
            kürzesten Pfades von einem Startknoten zu allen anderen Knoten in
            einem gewichteten Graphen. Er arbeitet dabei mit einer
            Prioritätswarteschlange, in der die Knoten nach ihrer Entfernung zum
            Startknoten sortiert sind. Der Algorithmus besucht jeden Knoten nur
            einmal und aktualisiert dabei laufend die Entfernungen zu den
            Nachbarknoten.
          </p>
          <p>Hier sind die Schritte des Dijkstra-Algorithmus:</p>
          <ol class="pl-10 space-y-3 list-decimal">
            <li>
              Initialisierung: Setze die Entfernung zum Startknoten auf 0 und
              die Entfernung zu allen anderen Knoten auf unendlich. Füge den
              Startknoten zur Prioritätswarteschlange hinzu.
            </li>
            <li>
              Solange die Prioritätswarteschlange nicht leer ist, nimm den
              Knoten mit der kürzesten Entfernung aus der
              Prioritätswarteschlange.
            </li>
            <li>
              Für jeden Nachbarknoten des aktuellen Knotens, berechne die
              Entfernung zum Startknoten durch Addition der Entfernung vom
              aktuellen Knoten zum Nachbarn und der Entfernung vom Startknoten
              zum aktuellen Knoten. Falls diese Entfernung kürzer ist als die
              aktuelle Entfernung zum Nachbarn, aktualisiere die Entfernung und
              füge den Nachbarn zur Prioritätswarteschlange hinzu.
            </li>
            <li>Wiederhole Schritt 2 und 3, bis alle Knoten besucht wurden.</li>
          </ol>
          <p>
            Am Ende des Algorithmus enthält jeder Knoten die Entfernung zum
            Startknoten und der kürzeste Pfad kann durch Rückverfolgung dieser
            Entfernungen ermittelt werden.
          </p>
          <ww-algographviz graph='{"newLink":"","nodes":[{"name":"Chen"},{"name":"Ana"},{"name":"Ethan"},{"name":"Frank"},{"name":"Hanes"}],"links":[{"source":"Ana","target":"Chen","weight":1},{"source":"Ana","target":"Frank","weight":1},{"source":"Chen","target":"Frank","weight":4},{"source":"Hanes","target":"Frank","weight":4},{"source":"Ana","target":"Ethan","weight":1}]}' algorithm="DIJKSTRA"></ww-algographviz>

  </body>
</html>