Shortest path

In graph theory, the shortest path problem finds a path between two vertices such that the weight of its edges is minimised. A few definitions:

• The problem operates on a weighted, directed graph $G=(V,E)$.
• A weight function maps edges to weights, $w:E\to \mathbb{R}$.
• The weight $w(p)$ of path $p=(v_0,v_1,\cdots ,v_k)$ is the sum of the weights of each constituent edge from vertices $(v_i,v_{i+1})$.

The shortest path is given by the smallest weight, i.e., the shortest-path weight from $u$ to $v$ is defined as:

$$\delta (u,v)=\{\begin{array}{llc}\min \{w(p):u\to v\}& & \text{if there is a path from}u\text{to}v\\ \infty & & \text{otherwise}\end{array}$$

What possible applications does this have?

• Mapping software direction planning
• FPGA routing
• Integrated circuit gate connections
• Internetworking, to deliver information from one computer to another

Some shortest path algorithms include:

• Bellman-Ford algorithm
• Dijkstra’s algorithm
• A-star algorithm

Variations

SSSP — single source to all vertices SDSP — single destination from all vertices reverse of SSSP single pair shortest path — from vertex $u$ to $v$ all pair — self explanatory we can use SSSP to solve all variants

bellman ford for each edge dijkstra’s for each vertex, store in matrix lookup matrix, s(u, v) + s(v, u) ⇒ take smallest dijkstra but we modify the relax function s -p→ u → v; either bottleneck is in p or in new edge (u, v)

relax(u, v, w)
	if (v.d < min(u.d, w(u, v)))
		v.d = min(u.d, w(u, v))
		v.pi = u

we initialise source with $\infty$, initialise everything else with 0