Posts tagged "graph search"

Shortest path, part I - Dijkstra's algorithm

Now that we have a way to represent graphs, we can discuss one of the most important problems in graph theory: the shortest path problem (SPP). More or less formally, we鈥檒l define SPP as:

Given a weighted graph G(V,E), find the sequence P = {v0, v1, v2, 鈥, v(n-1)}, vi 鈭 V, from vertex V0 to vertex V(n-1), such that the list of edges EP = {(v0,v1), (v1,v2), 鈥 (v(n-2), v(n-1))} exists and the summation of costs of all elements e 鈭 EP is the smallest possible.

In other words, find the less expensive (ergo 鈥渟hortest鈥) path between two vertices.

The trivial solution is using BFS starting at vertex A and stopping when it reaches vertex B. However, BFS doesn鈥檛 look at the edge costs: it calculates the path with least edges, not the path with least total cost.

Although not necessarily the fastest, Dijkstra鈥檚 algorithm is probably the most popular way to solve the shortest path problem due to its simplicity and elegance. The algorithm relies heavily on priority queues, so make sure to take a look at that if you haven鈥檛 already.

Pseudocode

dist[from] = 0
for v : G
      if v != source
            dist[v] = infinity
      prev[v] = -1
      PQ.add(v, dist[v])
while PQ.hasNext()
      u = PQ.pop()
      for each neighbor v of u
            alt = dist[u] + length(u, v)
            if alt < dist[v]
                  dist[v] = alt
                  prev[v] = u
                  PQ.decrease_key(v,alt)
return prev