Go - Finding the Shortest Path on a Graph

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