1.  Shortest path algorithms

• G is a digraph
• w(e) = weight of edge e
• P is a path
• w(P) = å_{i = 1}^k-1w(v_i® v_i+1)
• d(u,v) = min_{P:u® v}w(P) = weight of minimum weight path from u to v

There are several categories of weights:

• w(e) = 1 always (weights always the same)
• w(e) ³ 0 always (weights always positive)
• w(e) Î R (weights have any value)

In addition, there are 2 basic flavors of the algorithms

• single pair or single source
• all pairs

Here is a table of the algorithms which are used.

	w(e) = 1	w(e) ³ 1	w(e) Î R
Single	BreadthFirstSearch	Dijkstra	Bellman-Ford
all	BFS	Dijkstra	Johnson

2.  Rings

A ring is defined by R = (S,Å,Ä,0,1) where S is a set, Ä,Å:S²® S are binary operations. 0 is the identity element of Å and 1 the identity element of Ä. Rings also obey the following rules:

• (aÅb)Åc = aÅ(bÅc) and (aÄb)Äc = aÄ(bÄc) (associativity)
• aÅb = bÅa (commutativity)
• (aÅb)Äc = (aÄc)Å(bÄc) and aÄ(bÅc) = (aÄb)Å(aÄc) (distributivity)
• aÅ0 = 0Åa = a
• aÄ1 = 1Äa = a
• $(-a):aÅ(-a) = 0 (inverse)

A semiring must satisfy every requirement except for the last.

2.1  ring matrices

Given any ring a matrix ring, R^n×n = (S^n×n,Å^n×n,Ä^n×n,0^n×n,1^n×n) can be defined. 0^n×n is the 0 matrix and 1^n×n is the identity matrix. The addition operator is defined elementwise and the multiplication operator is defined as: A^n×nÄ^n×nB^n×n = Å_{k = 1}ⁿ(A_ikÄB_kj) .

2.2  ring examples

• Minimum weight paths can be defined using a ring (RÈ{¥},min,+,¥,0) .
• Another ring: (R⁺È{¥},max,*,0,1) .
• boolean ring: ({0,1},Ú,Ù0,1)
• (ZÈ{±¥},min,max,+¥,-¥)

2.3  Shortest path through rings

Consider the min,+ ring above. Construct an n×n ring from it. Assign the weights,

A_ij =

wij	if	(vi,vj) Î E
0	if	i = j
¥	else

To compute all pairs shortest paths, calculate A^n-1 .

2.4  timing analyses

The simplest way to calculate this is by multiply A together n-1 times which has cost O(n⁴) . This can be cut to O(n³log(n)) by doing the multiplications in a more clever order.