SHORTEST PATH ALGORITHMS

Shortest path algorithm is modeled as finding the shortest path between two nodes in weighted and directed network $G = (N,A)$ with a node set $N$ and an arc set $A$ as shown in Figure 1. Each arc $(i, j)\in A$ also has a length (or weight) $l_{ij} \geq 0$.

Figure 1: Weighted Graph

In the route finding context, the network is the road network. Nodes are the road junctions and arcs are road segments. The length of each arc could be the distance or travelling time between two adjacent junctions.

In this section, we review the two approaches. It is suggested that neither of the approaches is not suitable for route finding.