Single Source Shortest Path

Posted in Data structure by

A common problem is to find the shortest way from one to another point. Dijkstra created the solution, which is used as a basis for car navigation systems and traffic systems.

In a Graph are several nodes, one node can have a connection to another node, the cost of each connection can be expressed with a number.

The algorithm will be shown on this example graph: Node A: B->30, C->40 Node B: D->15 Node C: E->20 Node D: E->5 Node E: endpoint.

The initial node is A. There are two options. B and C. B is chosen, cause it cheaper. B saves 30 as meta data. There are two options again. A to C or B to D. The cost from A to C is 40. The cost from B to D is 30+15=45. A to C is chosen and C saves 40 as meta data. Next round uses B to D, cause it is cheaper then C to E. Last round uses D to E and the algorithm stops. Endpoint reached.

There are two common implementations: 1)adjacency matrix: uses a matrix to store costs between nodes, if no connection is available it is unlimited or undefined. Inefficient solution, cause it needs a lot of space and runtime O(n^2) 2)adjacency list and a heap priority queue: A bit harder to implement, but uses less space and the runtime is O(e log n).

The second implementation works by taking the node with minimal costs out of the priority queue. It searches for all possible direct connections to other nodes in the adjacency list. Uses the cheapest option. Puts it into the priority queue and updates the costs.

Published at , Updated at 2011-10-25

next: All Pairs shortest Path