DataMuseum.dk

top - metrics - download

    Length: 695 (0x2b7)
    Types: TextFile
    Names: »sp.web«

└─⟦52210d11f⟧ Bits:30007239 EUUGD2: TeX 3 1992-12
    └─⟦c319c2751⟧ »unix3.0/TeX3.0.tar.Z« 
        └─⟦036c765ac⟧ 
            └─⟦this⟧ »TeX3.0/Spiderweb/dijkstra/sp.web« 
└─⟦52210d11f⟧ Bits:30007239 EUUGD2: TeX 3 1992-12
    └─⟦63303ae94⟧ »unix3.14/TeX3.14.tar.Z« 
        └─⟦c58930e5c⟧ 
            └─⟦this⟧ »TeX3.14/Spiderweb/dijkstra/sp.web« 

TextFile

@*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.