Algorithms For Dummies

 

   

  PART 3 

 Exploring the World of Graphs

                           % to_next)

                    path[next_node] = actual_node

            last = actual_node

            known.add(actual_node)

    return priority.index, path

dist, path = dijkstra(graph, 'A', 'F')

Found shortcut from A to C

   Total length up so far: 3

Found shortcut from A to B

   Total length up so far: 2

Found shortcut from B to D

   Total length up so far: 4

Found shortcut from C to E

   Total length up so far: 5

Found shortcut from D to F

   Total length up so far: 7

Found shortcut from E to F

   Total length up so far: 6

The algorithm returns a couple of useful pieces of information: the shortest path 

to destination and the minimum recorded distances for the visited vertexes. To 

visualize the shortest path, you need a 

reverse_path

 function that rearranges the 

path to make it readable:

def reverse_path(path, start, end):

    progression = [end]

    while progression[-1] != start:

        progression.append(path[progression[-1]])

    return progression[::-1]

print (reverse_path(path, 'A', 'F'))

['A', 'C', 'E', 'F']

You can also know the shortest distance to every node encountered by querying 

the 

dist

 dictionary:

print (dist)

{'D': 4, 'A': 0, 'B': 2, 'F': 6, 'C': 3, 'E': 5}

---

CHAPTER 10