Problem: You want to find the shortest path between two nodes on a weighted graph.
Solution: Use Dijkstra’s algorithm to find the shortest path between two nodes. Dijkstra’s algorithm also uses a priority queue, which can be implemented using a min heap.
Plenty of algorithms rely on graphs. One of the most well - known algorithms on graphs is Dijkstra’s algorithm , sometimes called the shortest path algorithm . As the name suggests, this simple yet effective algorithm finds the shortest path between two nodes in a graph.
Say you want to travel from London to Istanbul and you figure out the following possible routes through the different major cities in Europe. Figure 14 - 10 shows a map of Europe, with the cities as nodes of a weighted directed graph, and flight routes between them as edges. The flight times between two cities are the edge weights.
You have figured out the amount of time to fly from these cities to other cities but now you want to find the shortest amount of time needed to travel from London to Istanbul.
This is where Dijkstra’s algorithm comes in handy, and it’s probably the most popular algorithm to solve the shortest path problem. The algorithm itself is quite simple. Dijkstra famously came up with the algorithm without pen and paper, in about 20 minutes, while accompanying his fiancee shopping in Amsterdam.
You need two data structures for Dijkstra’s algorithm — a weighted graph and a min heap. The only change you need is the Node struct in the weighted graph, to add a through pointer to a Node . This field, when not nil, points to the previous node in the shortest path:
type Node struct { name string value int through * Node }
Before you start with the algorithm, you need to populate the graph accordingly:
func buildGraph () * Graph { graph := NewGraph () nodes := make ( map [ string ] * Node ) names := [] string { "London" , "Paris" , "Amsterdam" , "Luxembourg" , "Zurich" , "Rome" , "Berlin" , "Vienna" , "Warsaw" , "Istanbul" } for _ , name := range names { n := & Node { name , math . MaxInt , nil } graph . AddNode ( n ) nodes [ name ] = n } graph . AddEdge ( nodes [ "London" ], nodes [ "Paris" ], 80 ) graph . AddEdge ( nodes [ "London" ], nodes [ "Luxembourg" ], 75 ) graph . AddEdge ( nodes [ "London" ], nodes [ "Amsterdam" ], 75 ) graph . AddEdge ( nodes [ "Paris" ], nodes [ "Luxembourg" ], 60 ) graph . AddEdge ( nodes [ "Paris" ], nodes [ "Rome" ], 125 ) graph . AddEdge ( nodes [ "Luxembourg" ], nodes [ "Berlin" ], 90 ) graph . AddEdge ( nodes [ "Luxembourg" ], nodes [ "Zurich" ], 60 ) graph . AddEdge ( nodes [ "Luxembourg" ], nodes [ "Amsterdam" ], 55 ) graph . AddEdge ( nodes [ "Zurich" ], nodes [ "Vienna" ], 80 ) graph . AddEdge ( nodes [ "Zurich" ], nodes [ "Rome" ], 90 ) graph . AddEdge ( nodes [ "Zurich" ], nodes [ "Berlin" ], 85 ) graph . AddEdge ( nodes [ "Berlin" ], nodes [ "Amsterdam" ], 85 ) graph . AddEdge ( nodes [ "Berlin" ], nodes [ "Vienna" ], 75 ) graph . AddEdge ( nodes [ "Vienna" ], nodes [ "Rome" ], 100 ) graph . AddEdge ( nodes [ "Vienna" ], nodes [ "Istanbul" ], 130 ) graph . AddEdge ( nodes [ "Warsaw" ], nodes [ "Berlin" ], 80 ) graph . AddEdge ( nodes [ "Warsaw" ], nodes [ "Istanbul" ], 180 ) graph . AddEdge ( nodes [ "Rome" ], nodes [ "Istanbul" ], 155 ) return graph }
Now that you have the graph, take a look at Dijkstra’s algorithm:
func dijkstra ( graph * Graph , city string ) { visited := make ( map [ string ] bool ) heap := & Heap {} startNode := graph . GetNode ( city ) startNode . value = 0 heap . Push ( startNode ) for heap . Size () > 0 { current := heap . Pop () visited [ current . name ] = true edges := graph . Edges [ current . name ] for _ , edge := range edges { if ! visited [ edge . node . name ] { heap . Push ( edge . node ) if current . value + edge . weight < edge . node . value { edge . node . value = current . value + edge . weight edge . node . through = current } } } } }
Here is how it works. Let’s say you want to find the shortest travel time from London to Istanbul:
1 Set up the weighted graph, a min heap, and a map to mark cities that have been visited before.
2 Get the origin node, London, set its node value to 0, and push it into the heap.
3 The next step is a loop. While the heap is not empty, you pop the heap. This will be your current node.
4 Mark the city as visited.
5 For each city that the current node is connected to (Paris, Luxembourg, and Amsterdam for London), push the city into the heap if it’s not been visited before.
6 Check if the current node’s value plus the edge’s weight is less than the connected node’s (Paris, Luxembourg, and Amsterdam) value.
7 If it is, set the connected node’s value to the current node’s value plus the edge’s weight. This is why you set every node (except the originating node, London) to be MaxInt .
8 Set the connected node’s through field to be the current node. The through field tells you which node the shortest path to this node is, so you can trace back later to come up with the path.
9 Once you’re done, loop from step 3 until all the nodes are visited.
That’s it for the algorithm. Here’s how you can use it:
func main () { // build and run Dijkstra's algorithm on graph graph := buildGraph () city := os . Args [ 1 ] dijkstra ( graph , city ) // display the nodes for _ , node := range graph . Nodes { fmt . Printf ( "Shortest time from %s to %s is %d\n" , city , node . name , node . value ) for n := node ; n . through != nil ; n = n . through { fmt . Print ( n , " <- " ) } fmt . Println ( city ) fmt . Println () } }
Build the graph and pass it to the algorithm. The results are all in the nodes. After calling the dijkstra function, the values of the nodes are now the shortest flight times needed to travel from London while the through fields are the previous nodes that will link back to the shortest path.
If you take the nodes and walk backward to London, you’ll see the shortest path:
$ % go run dijkstra.go London Shortest time from London to London is 0 London Shortest time from London to Paris is 80 Paris <- London Shortest time from London to Amsterdam is 75 Amsterdam <- London Shortest time from London to Luxembourg is 75 Luxembourg <- London Shortest time from London to Zurich is 135 Zurich <- Luxembourg <- London Shortest time from London to Rome is 205 Rome <- Paris <- London Shortest time from London to Berlin is 160 Berlin <- Amsterdam <- London Shortest time from London to Vienna is 215 Vienna <- Zurich <- Luxembourg <- London Shortest time from London to Warsaw is 240 Warsaw <- Berlin <- Amsterdam <- London Shortest time from London to Istanbul is 345 Istanbul <- Vienna <- Zurich <- Luxembourg <- London