Shortest Path – Python

August 24, 2010 – 2:26 pm

Problem: Write a python function to calculate the shortest path given a start node (or vertex), an end node and a graph. Use Dijkstra’s algorithm. Return the distance from the start node to the end node, as well as the path taken to get there.

The implementation below sticks pretty closely to the algorithm description in the wikipedia entry, which I turned into something a little more pseudo-code-ish to help me implement it:

Initial state:

  1. give nodes two properties – node.visited and node.distance
  2. set node.distance = infinity for all nodes except the start node which is set to zero.
  3. set node.visited = false for all nodes
  4. set current node = start node.

Current node loop:

  1. if current node = end node, finish and return current.distance & path
  2. for all unvisited neighbors, calc their tentative distance (current.distance + edge to neighbor).
  3. if tentative distance < neighbor's set distance, overwrite it.
  4. set current.isvisited = true.
  5. set current = remaining unvisited node with smallest node.distance

Here’s my implementation – it’s recursive, as suggested by the algorithm description:

import sys
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
    """Find the shortest path between start and end nodes in a graph"""
    # detect if it's the first time through, set current distance to zero
    if not visited: distances[start]=0
    if start==end:
        # we've found our end node, now find the path to it, and return
        while end != None:
        return distances[start], path[::-1]
    # process neighbors as per algorithm, keep track of predecessors
    for neighbor in graph[start]:
        if neighbor not in visited:
            neighbordist = distances.get(neighbor,sys.maxint)
            tentativedist = distances[start] + graph[start][neighbor]
            if tentativedist < neighbordist:
                distances[neighbor] = tentativedist
    # neighbors processed, now mark the current node as visited
    # finds the closest unvisited node to the start
    unvisiteds = dict((k, distances.get(k,sys.maxint)) for k in graph if k not in visited)
    closestnode = min(unvisiteds, key=unvisiteds.get)
    # now we can take the closest node and recurse, making it current
    return shortestpath(graph,closestnode,end,visited,distances,predecessors)

if __name__ == "__main__":
    graph = {'a': {'w': 14, 'x': 7, 'y': 9},
            'b': {'w': 9, 'z': 6},
            'w': {'a': 14, 'b': 9, 'y': 2},
            'x': {'a': 7, 'y': 10, 'z': 15},
            'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11},
            'z': {'b': 6, 'x': 15, 'y': 11}}
    print shortestpath(graph,'a','a')
    print shortestpath(graph,'a','b')

        (0, ['a'])
        (20, ['a', 'y', 'w', 'b'])

You’ll see I turned the example in wikipedia into a graph for the test case in the code above.

I found this useful about how to represent and process graphs in python: I think this was written by Guido himself.

There’s a bunch of interesting implementations on the web, including two here. More elegant, but it took me a while to understand them.

  1. 15 Responses to “Shortest Path – Python”

  2. Hey there,

    I was wondering… This looks pretty cool and I’d like to know how to make it work with cities and distances like this:

    NewYork Chicago 200
    Chicago LA 100
    Chicago SanFrancisco 1000
    SanFrancisco Florida 1400

    This means, that the distance from NewYork to Chicago is 200, Chicago to LA is 100, etc. Note: Chicago to NewYork is unknown we only know NewYork to Chicago.

    Then the user inputs ‘END’ and in each line the starting city and finishing city, respectively.

    f = []
    while True:
    a = raw_input()
    if a == ‘FIM’:

    city1 = raw_input()
    city2 = raw_input()

    This would work and create an array with all of them.

    My question is how to “Convert” that array to a dictionary usable by this function?

    Here’s an example of how the array would be:

    NewYork Chicago 200
    Chicago LA 100
    Chicago SanFrancisco 1000
    SanFrancisco Florida 1400

    [‘NewYork Chicago 200’, ‘Chicago LA 100’, ‘Chicago SF 100’, ‘SF Florida 1400’]

    Thanks much for your time.

    By Omicron Alpha on Mar 3, 2011

  3. Can I get your email address, I need help to find out maximum capacity path from a source node to all other nodes.

    By Dip on Apr 28, 2011

  4. I think you have a bug:

    If start == end at first iteration:

    print shortestpath(graph,’a’,’a’)

    Traceback (most recent call last):
    File “./”, line 39, in
    print shortestpath(graph,’a’,’a’)
    File “./”, line 13, in shortestpath
    return distances[start], path[::-1]
    KeyError: ‘a’

    You need to init distances[] before enter while() loop.

    By Int-0 on May 31, 2011

  5. Thanks Int-0
    Now fixed.

    my email address is in the about page of the blog.

    By nolfonzo on Jun 18, 2011

  6. You should use float(“inf”) (aka python’s infinity) instead sys.maxint (a fixed value). Remember in python ints are automatically parsed to longs when required, so you can raise easily maxint on a graph without overflows.

    By Spayder26 on Jun 28, 2011

  7. if i want all shortest path.
    How to edit this?

    By nat on Nov 30, 2011

  8. There is a bug in your code.

    Using mutable objects as default values in your function definition may cause it to execute correctly only the first time it is called in a program, any subsequent calls that receive different input data may fail or return incorrect values.

    This is because the function arguments that are mutable objects will carry over their contents to subsequent calls of this function if those arguments are omitted, they are not initialized to the default values in your function definition, as you are intending. The default values of mutable objects are only used when the function is first called in a program.

    This behaviour is by design, see-

    This behaviour can be avoided by not relying on the default argument values when calling the function, ie. always include all argument values that are mutable.

    By Boogs on Dec 24, 2012

  9. Every weekend i used to go to see this site, for the reason that i want enjoyment, since this this website conations in fact good funny information too.

    By running shoes reviews 2014 on Aug 12, 2014

  10. Hey! This is my first visit to your blog! We are a team of volunteers and starting a new project in a community
    in the same niche. Your blog provided us valuable information to work on. You
    have done a wonderful job!

    By Chara on Sep 9, 2014

  11. Can I simply say what a relief to discover someone that really knows what they’re discussing
    on the net. You certainly know how to bring an issue to
    light and make it important. More and more people really need to look at this and understand
    this side of the story. I was surprised you are not more popular given that you definitely possess the

    By Starla on Oct 9, 2015

  12. I am really pleased to glance at this web site posts which carries plenty of useful facts,
    thanks for providing such data.

    By Addie on Oct 13, 2015

  13. My brother recommended I may like this website. He was once totally right.
    This post truly made my day. You can not consider just how so much time I had spent for this info!
    Thank you!

    By sega circolare on Oct 29, 2015

  14. Hello there I am so delighted I found your blog page, I really found you by error, while I was searching on Yahoo for
    something else, Anyways I am here now and would
    just like to say thank you for a remarkable post and a all round enjoyable
    blog (I also love the theme/design), I don’t have time to go through it
    all at the moment but I have bookmarked it and also included your RSS feeds, so
    when I have time I will be back to read more, Please do keep up
    the great jo.

    By on Oct 31, 2015

  15. Hello very cool blog!! Man .. Beautiful ..
    Wonderful .. I’ll bookmark your web site and take the feeds additionally?
    I’m glad to find so many helpful info here in the
    post, we want develop more strategies in this regard, thanks for sharing.
    . . . . .

    By cardiofrequenzimetro on Nov 4, 2015

  16. Because the admin of this site is working, no doubt very soon it will be famous,
    due to its feature contents.

    By on Nov 22, 2015

Post a Comment