Dijkstra's algorithm in Maple

> restart;

> with(networks);

The following procedure is an implementation of Dijsktra's algorithm for finite, simple, undirected graphs. Actually, the same algorithm would work for directed graphs as well, but the program would have to be modified slightly to account for the way Maple deals with directed and undirected edges. It would be easy to extend the algorithm to multigraphs as well.

>    dijkstra:=proc(G::graph, x)

  # G is our graph, and x is the starting vertex

  # weight is a local procedure which returns the weight of the edge
  #   from u to v, or infinity if there is no such edge
  # L(v) is a table of temporary distances from x, where we store the
  #   length of the shortest path found SO FAR from x to v
  # K(v) is a table where we store the predecessor of v in the shortest
  #   path found SO FAR from x to v
  # P is a set which contains the k closest vertices to x
  # Q is the complement of P (it's used for efficiency, so we don't have
  #   to compute the complement of P repeatedly)
  # v and u are temporary variable used in loops that run over vertices

  local weight,L,K,P,Q,v,u;

  weight:=proc(G::graph, u, v)

    # Check if there is an edge from u to v. If not return infinity,
    # otherwise return the weight of that edge
    # Edges({u,v},G) returns the set of all edges between u and v.
    if edges({u,v},G)={} then
      return infinity;
    else
      return eweight(edges({u,v},G)[1],G);
      # Since G is simple, edges({u,v},G) will have exactly one element,
      # but it's still formally a set, so we have to pick its first element
      # eweight returns the weight of an edge in G
    end if;
  end proc;

  # Initialization
  P:={};                     # Set P = empty set
  Q:=vertices(G);            # Set Q = set of all verices
  L:=table();
  K:=table();
  for v in vertices(G) do
    L[v]:=infinity;          # Set all the L(v) to infinity
  end do;
  L[x]:=0;                   # The distance of x from itself is 0
  u:=x;                      # x will be the first vertex we move to P

  # Main loop of the algorithm continues until the next closest vertex
  # is infinitely far from x, that is there is no path from x to it
  while L[u]<infinity do
    P:=P union {u};   # u is the next closest vertex to x, move it to v
    Q:=Q minus {u};   # and remove it from Q
    if Q={} then
      break;          # If there are no more vertices left, quit the loop
    end if;

    # The next loop updates the temporary weights on the vertices if there
    # is a shorter path from x to v via u than the shortest known so far
    for v in Q do
      if L[u]+weight(G,u,v) < L[v] then
        L[v]:=L[u]+weight(G,u,v);
        K[v]:=u;
      end if;
    end do;

    # We need to find a vertex with the shortest temporary distance from x
    u:=Q[1];
    for v in Q do
      if L[v]<L[u] then
        u:=v;
      end if;
    end do;
    # u is the next closest vertex to x

  end do;
  return [L,K]; # Return an array whose elements are the tables L and K
end proc;

This next procedure takes the output of dijkstra and two vertices u and v and returns a shortest path from u to v

>    listpath:=proc(lk,u,v)

  local p;

  # First we check if there is even a path from u to v
  if lk[1][v]=infinity then
    error("There is no path from %1 to %2.", u, v);
  end if;
  # If u=v then the path consists of the vertex u, otherwise do recursion
  if u=v then
    return [u];
  else
    return [listpath(lk,u,lk[2][v])[], v];
  end if;
end proc;

The graph from 3.3.11

> gr1:=graph({A, B, C, D, E, F, G, H, I, S},{{A,D}, {A,G}, {B,G}, {B,I}, {C,D}, {C,E}, {C,S}, {D,F}, {E,F}, {E,H}, {F,G}, {F,I}, {H,I}, {H,S}});

> W:=eweight(gr1);

> W[e1]:=5: W[e2]:=1: W[e3]:=2: W[e4]:=4: W[e5]:=2: W[e6]:=1: W[e7]:=3: W[e8]:=1: W[e9]:=2: W[e10]:=1: W[e11]:=1: W[e12]:=3: W[e13]:=1: W[e14]:=5:

> draw(Linear([S], [C,E,H], [D,F,I], [A,G,B]), gr1); # Unfortunately, Maple doesn't draw the edge weights