Shortest path problem

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