Single-Source Shortest Path

Directed graph G= (V,E)

Path from u to v

Before: length of path = number of edges
Cost C: E -> R⁺

Length(or cost) of path: sum of costs of edges on path

from--to	nodes in path	length
1--2:	1,3,2	25
1--3:	1,3	15
1--4:	1,4	20
1--5:	1,3,2,5	40

Shortest path from a single source node to all other nodes.

See also Figure 18.9

Rationale/Premises

P₁: proposed shortest path from v₀ to v. Path P₁ includes the subpath from v₀ to u of distance d₁

If d₂ < d₁, then P₁ is not a shortest path from v₀ to v.

Lemma: If v₀, v₁, v₂..., v_k, P is a shortest path from v₀ to v_k, then v₀, v₁,..., v_i is a shortest path from v₀ to v_i for all 1 < i < k
(shortest total is shortest all along way) Dynamic programming

Also, dist (v₀,v₁) < dist (v₀,v₂) < .... < dist (v₀,v)

Technique - Greedy Method:

Scan graph for nodes within a given radius of v₀

Thus first find shortest path for each intermittent stop possible. Keep increasing radius.

S = set of nodes for which shortest paths have been computed.

The next node to be included must be the one with the shortest path from v₀ among all nodes not in S.

Let this node be v.

All intermediate nodes on the shortest path from v₀ to v must belong to S.

S -- set of nodes "closest" to v₀ for which shortest paths have already been computed.

v <- next node to be included in S.

Greedy: v is that node in V-S closest to v₀

Dist (u)<-- cost of shortest path from v₀ to u passing only through nodes in S. (for all u V)

Once v is included in S, distances will have to be corrected. So each time we put a vertex v in, we have to check all vertices v is connected to, and increment Dist(u)

Dijkstra's shortest path

• performs a "best-first"/greedy search from start vertex S to end vertex T.

• each edge (V,W) in a graph has a distance dist(V,W) or weight associated with it.

• for each node V in the graph associate:
  1. pathlength-- length of shortest path thus far from S to V

  2. pathpred-- the predecessor of V along that path

  3. Boolean certain-- true if path certifiably shortest overall

Dijkstra's Shortest Path Algorithm: (obviously pseudocode - I will let you implement it in Java readme)

method ShortestPath (Vertex S,T);						
 Begin
	For each vertex Vi in V (in G) 	// initialize
		Begin
			Pathlength (Vi) = infinity;
			Pathpred (Vi) = Undefined;
			Certain (Vi) = False;
		End
	Pathlength (S)=0;
	Nextodo={S};

    While NotCertain (T) do
	Begin
   		Pick vertex Vi in Nextodo with shortest pathlength;
   		Certain (Vi)= true;
   		for each neighbor Wj of Vi
			if Pathlength (Wj) > (Pathlength (Vi) + Dist (Vi,Wj))  then
	  			begin
				Pathlength (Wj) = Pathlength (V)+ Dist (Vi,Wj);
				Pathpred (Wj) = Vi;
	  			end;
		Nextodo = Nextodo - Vi + {neighbors of Vi which are not Certain}

  	End;
End;

Next To Do	Certain	Pathlength	Pathpred
		Of:     Is:	Of:     Is:

Try first yourself, and then see this chart Filled in

O(n²)

Outside: While loop O(n)

Inside:
Check each neighbor (if complete could be all)
Update pathlengths for all
O(2n) or O(n)

Dijkstra Quotes: "If you don't know what your program is supposed to do, you'd better not start writing it."

"The question of whether a computer can think is no more interesting than the question of whether a submarine can swim."

Additional tidbits a long time ago and more quotes

Fine, let's talk about object implementation.

Alternative Code in book on page 725.

We have Graphs, Vertices, Edges, Paths.

Should they be their own objects?

What information goes in these?

• Graphs have IVs of Vertices and Edges (this is what defines a graph). Possibly Paths, Articulation Points, etc. (the class would have a method that calculates these, but one might want to store them in IVs too - depends on use)

• Edges will have costs (or lengths)
  Should I just represent an edge as a triplet? (x,y,c) or should it be an object with two vertices and a cost

• Paths will have a set of vertices and a distance
  Should they be temporary variables inside code? or should they be their own class with instances that hold information for later use?

By the way: BF and DF numbering

0(n+ e)

Java applet for Dijksta's Shortest Path See demos on left. (A (6,10) graph means 6 vertices and 10 edges)