summaryrefslogtreecommitdiff
path: root/web/spiderweb/src/dijkstra/sp.web
diff options
context:
space:
mode:
Diffstat (limited to 'web/spiderweb/src/dijkstra/sp.web')
-rw-r--r--web/spiderweb/src/dijkstra/sp.web28
1 files changed, 28 insertions, 0 deletions
diff --git a/web/spiderweb/src/dijkstra/sp.web b/web/spiderweb/src/dijkstra/sp.web
new file mode 100644
index 0000000000..9725b2ac10
--- /dev/null
+++ b/web/spiderweb/src/dijkstra/sp.web
@@ -0,0 +1,28 @@
+@*Dijkstra's shortest path.
+Obviously the way to prove Dijkstra's algorithm is the way Dijsktra
+would do it himself.
+Consider
+@u
+@<Set |d[u]| to all $\infty$ for all |u| in |V| @>@;
+d[v] := 0;
+W := {v};
+@<For each |u| in |V-W| and $(v,u) \in E$
+ let |d[u]| be the weight of $(v,u)$@>@;
+{@tinvariant: $\forall u \in W$,
+ $d[u]$ is the shortest distance from $v$ to $u$@> &
+ @t$\forall u \in V-W$, $d[u] }
+do |W| != |V| -->
+ @<Let |u| be a vertex in |V-W| with |d[u]| as small as possible@>@;
+ @<For each |w| in |V-W| and $(u,w) \in E$@>@;
+ if d[w] <= d[u] + c(u,w) --> skip
+ [] d [w] >= d[u] + c(u,w) --> d[w] := d[u] + c(u,w)
+ fi;
+ W := W @t$\cup$@> {u}
+od
+
+@*Index.
+
+
+
+
+