title: Dijkstra's Algorithm Implementation in Python - How Does it Work?
body: <p>I can use the following English algorithm to find shortest paths using Dijkstra's Algorithm on paper:</p>
  
  <ul>
  <li><p>Step 1:    Assign permanent label and order to starting node</p></li>
  <li><p>Step 2:    Assign temporary labels to all nodes directly reached by starting node</p></li>
  <li><p>Step 3:    Select the lowest temporary label and make it permanent</p></li>
  <li><p>Step 4:    Assign an order to the node</p></li>
  <li><p>Step 5:    Update and assign temporary labels for nodes directly reached from the new permanent node</p></li>
  <li><p>Step 6:    Repeat steps 3, 4 &amp; 5 until the destination node is made permanent</p></li>
  </ul>
  
  <p>I have searched for a Python implementation and many are quite complex or use data structures I'm not familiar with. Eventually I found the one below. I have spent quite some time tracing it's execution in a Python visualizer, and I can get a sense of how it works but it has not yet clicked for me.</p>
  
  <p>Could someone please explain how the code relates to the English algorithm? For example, how does the notion of "predecessors" relate to the "permanent labels" in the English version?</p>
  
  <pre><code>from math import inf
  
  graph = {'a':{'b':10,'c':3},'b':{'c':1,'d':2},'c':{'b':4,'d':8,'e':2},'d':{'e':7},'e':{'d':9}}
  
  
  def dijkstra(graph,start,goal):
      shortest_distance = {}
      predecessor = {}
      unseenNodes = graph
      infinity = inf
      path = []
      for node in unseenNodes:
          shortest_distance[node] = infinity
      shortest_distance[start] = 0
  
      # Determine which is minimum node. What does that mean?
      while unseenNodes:
          minNode = None
          for node in unseenNodes:
              if minNode is None:
                  minNode = node
              elif shortest_distance[node] &lt; shortest_distance[minNode]:
                  minNode = node
  
          for edge, weight in graph[minNode].items():
              if weight + shortest_distance[minNode] &lt; shortest_distance[edge]:
                  shortest_distance[edge] = weight + shortest_distance[minNode]
                  predecessor[edge] = minNode
          unseenNodes.pop(minNode)
  
      currentNode = goal
      while currentNode != start:
          try:
              path.insert(0,currentNode)
              currentNode = predecessor[currentNode]
          except KeyError:
              print('Path not reachable')
              break
      path.insert(0,start)
      if shortest_distance[goal] != infinity:
          print('Shortest distance is ' + str(shortest_distance[goal]))
          print('And the path is ' + str(path))
  
  
  dijkstra(graph, 'a', 'b')
  </code></pre>