title: Modifying Dijkstra's algorithm for least changes
body: <p>I'm using a version of Dijkstra's algorithm written in Python which I found online, and it works great. But because this is for bus routes, changing 10 times might be the shortest route, but probably not the quickest and definitely not the easiest. I need to modify it somehow to return the path with the least number of changes, regardless of distance to be honest (obviously if 2 paths have equal number of changes, choose the shortest one). My current code is as follows:</p>
  
  <pre><code>from priodict import priorityDictionary
  
  def Dijkstra(stops,start,end=None):
      D = {}  # dictionary of final distances
      P = {}  # dictionary of predecessors
      Q = priorityDictionary()   # est.dist. of non-final vert.
      Q[start] = 0
  
      for v in Q:
          D[v] = Q[v]
          print v
          if v == end: break
  
          for w in stops[v]:
              vwLength = D[v] + stops[v][w]
              if w in D:
                  if vwLength &lt; D[w]:
                      raise ValueError, "Dijkstra: found better path to already-final vertex"
              elif w not in Q or vwLength &lt; Q[w]:
                  Q[w] = vwLength
                  P[w] = v
      return (D,P)
  
  def shortestPath(stops,start,end):
      D,P = Dijkstra(stops,start,end)
      Path = []
      while 1:
          Path.append(end)
          if end == start: break
          end = P[end]
      Path.reverse()
      return Path
  
  stops = MASSIVE DICTIONARY WITH VALUES (7800 lines)
  print shortestPath(stops,'Airport-2001','Comrie-106')
  </code></pre>
  
  <p>I must be honest - I aint no mathematician so I don't quite understand the algorithm fully, despite all my research on it.</p>
  
  <p>I have tried changing a few things but I don't get even close.</p>
  
  <p>Any help? Thanks!</p>