NB: If you need to revise how Dijstra's work, have a look to the post where I detail Dijkstra's algorithm operations step by step on the whiteboard, for the example below.
First, let's choose the right data structures. The implementation can be a nightmare if you pick a bad data structure for describing the graphs. In python, the dict structure is particularly handy, so let's use it.
On the above example, s has two neighbors a and b, linked with cost 2 and 1 respectively. So, our graph dictionary will look like this:
graph = {'s': {'a': 2, 'b': 1},
'a': {'s': 3, 'b': 4, 'c':8},
'b': {'s': 4, 'a': 2, 'd': 2},
'c': {'a': 2, 'd': 7, 't': 4},
'd': {'b': 1, 'c': 11, 't': 5},
't': {'c': 3, 'd': 5}}
Now, if you have followed my previous post detailing the pseudo code and operations of Dijsktra's shortest path tree algorithm, you know that we need to keep track of the following information:- which nodes are not visited yet: we can use a list for that.
- a predecessor and a cost for every node. Let's use dict type for these elements, it will ease our life when we look up their value for a given node.
So the signature of our function is the following:
def shortestpath(graph,src,dest,visited=[],distances={},predecessors={}):
It will return the shortest path from src to dest, but could as well return a shortest path tree.
You will need to know the two following python functions to implement Dijkstra smartly.
mydict.get(mykeyvalue,17)this function of a dict element (here 'mydict') searches for the value of the dict for the keyvalue 'mykeyvalue'. If this key does not exist in the dict, the function does not raise an error. Instead, it returns the value provided as the second argument, here 17.
min(mydict, key=mydict.get)The min function can be applied on dictionaries! You just have to specify the key function as in the above example.
Now, we have everything we need to implement the function. I propose that you try it on your side and then look at the solution. Otherwise, you'll not memorize the algorithm. That being said, it's your choice...
One last thing before jumping to the code: if your graph bears negative weights, Dijkstra's algorithm will run into trouble - you should rather use Floyd or Bellman-Ford algorithm, which are able to detect negative cycles in graphs. Remember that Dijsktra's algorithm is for graphs with positive weights only.
def dijkstra(graph,src,dest,visited=[],distances={},predecessors={}):
""" calculates a shortest path tree routed in src
"""
# a few sanity checks
if src not in graph:
raise TypeError('The root of the shortest path tree cannot be found')
if dest not in graph:
raise TypeError('The target of the shortest path cannot be found')
# ending condition
if src == dest:
# We build the shortest path and display it
path=[]
pred=dest
while pred != None:
path.append(pred)
pred=predecessors.get(pred,None)
# reverses the array, to display the path nicely
readable=path[0]
for index in range(1,len(path)): readable = path[index]+'--->'+readable
#prints it
print('shortest path - array: '+str(path))
print("path: "+readable+", cost="+str(distances[dest])) else :
# if it is the initial run, initializes the cost
if not visited:
distances[src]=0
# visit the neighbors
for neighbor in graph[src] :
if neighbor not in visited:
new_distance = distances[src] + graph[src][neighbor]
if new_distance < distances.get(neighbor,float('inf')):
distances[neighbor] = new_distance
predecessors[neighbor] = src
# mark as visited
visited.append(src)
# now that all neighbors have been visited: recurse
# select the non visited node with lowest distance 'x'
# run Dijskstra with src='x'
unvisited={}
for k in graph:
if k not in visited:
unvisited[k] = distances.get(k,float('inf'))
x=min(unvisited, key=unvisited.get)
dijkstra(graph,x,dest,visited,distances,predecessors)
if __name__ == "__main__":
#import sys;sys.argv = ['', 'Test.testName']
#unittest.main()
graph = {'s': {'a': 2, 'b': 1},
'a': {'s': 3, 'b': 4, 'c':8},
'b': {'s': 4, 'a': 2, 'd': 2},
'c': {'a': 2, 'd': 7, 't': 4},
'd': {'b': 1, 'c': 11, 't': 5},
't': {'c': 3, 'd': 5}}
dijkstra(graph,'s','t')
And magic... It returns:
shortest path: ['t', 'd', 'b', 's'] cost=8
Well done and congratulations for reading this post to the end! Now, if you are working on Dijsktra's algorithm, I think you are preparing for an interview at Google, Microsoft, or Amazon. Am I right?
Then, the best tip I can give you is to look at two books "Cracking the PM Interview: How to Land a Product Manager Job in Technology" and "Cracking the Coding Interview: 150 Programming Questions and Solutions". They were written by Gayle Laakmann McDowell, a former recruiter from Google who also worked at Apple and I find them really great!
I hope this post has helped you. If you like it, please share it on social media and you will make my day! Thanks!
PS: I love your comments and I must apologize for not being able to answer them all. I have a demanding job and family. Thank you for your understanding!
Hi,
ReplyDeleteIf I am given an input as the following:
node1, node2, length1
node2, node3, length2
node1, node3, length3
How do I create a nested dictionary like your graph?
Thank you very much for your help.
Hello,
ReplyDeleteyour question is incomplete, sorry! What's your data structure in input? A string, an array, ... This point conditions the conversion method to the nested dictionary format I propose. Anyway it should be pretty easy: a loop to go through your input and fill in the nested dictionary appropriately.
dic={}
ReplyDeletedef add_dic(node1,node2,length):
if node1 not in dic:
dic[node1]={}
dic[node1][node2]=length
else:
dic[node1].update({node2:length})
what if there won't be any path between s and t ?
ReplyDeleteGood question :) In such case, the path has an infinite cost.
Deletethanks alot and i really love the outlook of your blog. please can you teach me how to design my this way
ReplyDeleteThank you for this article.
ReplyDeleteI used it in my code and saved a lot of time :)
I have to make a comment though: the end condition is not ok. Now it ends when it reaches the destination and if there is a shorter path it won't find it. I came around such a case. The proper end is when there are no more unvisited nodes. Then all the posibile distances are computed.
There is a catch: you can't return the path in this case. Not without some othere modifications. (I didn't need the path so I skipped it)
I just wanted to tell you this. Maybe it will help you like it helped me :)
Actually, your wrong. Dijkstras algorithm builds upon the paths it already has and in such a way that it extends the shortest path it has. Hence, upon reaching your destination you have found the shortest path possible. This is the strength of Dijkstra's algorithm, it does not need to evaluate all nodes to find the shortest path from a to b. Of course, this only works if the distances between nodes are only positive.
DeleteUgh, you're*
DeleteCan you suggest why this error occurs? It does not occur in the previous use of ('inf').
ReplyDeleteunvisited[k] = distances.get(k,float('inf'))
TypeError: list indices must be integers, not str
Hi,
ReplyDeleteI tried changing print to return, but it gave me none, is there way to return the values instead?
Just having a look at this now, hopefully you sorted this. For those people who haven't you'll need to return the value in both the if src==dest & else clauses as otherwise your output will get lost somewhere in the stack.
DeleteSo change the print statement to:
return path, distances[dest]
and the recursion to:
return dijkstra(graph, x, dest, visited, distances, predecessors)
this is my input 1->7 7->2 2->5 5->6
ReplyDeletei need output 7->1->2->5->6
how do i change this algorithm to obtain this output
Hi,
ReplyDeleteWhat is the time complexity for this implementation?
Hi,
ReplyDeleteWhen I run the programme a couple of times then the following error pops up:
File "C:/Users/brams/Desktop/Network scheduling/Code/dijkstrasalgoritm.py", line 88, in dijkstra
x = min(unvisited, key=unvisited.get)
ValueError: min() arg is an empty sequence
What can I do about this?
How about plain old debugging? Start by printing the value of the variables triggering hte issue?
DeleteI'll pile on to the above. I've tested with multiple graphs and it has both given error above and given incorrect answers. Don't think this code is perfectly implemented.
DeleteThis was fantastic! Worked like a charm for one of the Project Euler problems (I was stuck on it for a while). Thanks for taking the time to share it -- you made my day.
ReplyDeleteI tried to run the algorithm, but the line:
ReplyDeleteif __name__ == "__main__":
results to an "syntax error".
Can anyone help?
Excuse my, I am surely stupid but your code say :"shortest path: ['t', 'd', 'b', 's'] cost=8" or it seems to me that the path ['t', 'd', 'b', 's'] has a cost of 5 + 1 + 4 = 10 and that the path ['t', 'c', 'a', 's'] with a cost of 3 + 2 + 3 = 8 is shorter. Can you explain me where is my mistake. Thank you. Pascal Grandeau
ReplyDeleteHello Anonymous,
ReplyDeletewe are reading the same path but in different directions :) in the array t d b s the target t is in the first position whereas the source is in the last position. Stated differently, t d b s array refers to the path s ---1--> b ----2-> d ----5----> t with a total cost of 8. You were reading the reverse path, which indeed as a cost of 10 but is not the one we were looking for as its start is not s (s is its destination) and as you noted, it is not even a shortest path.
I hope this helps!
PS: to other commentators, all my apologies but a busy job and babies do not usually allow me to answer to comments.
PS: I have updated the code above to add the display of the final path in a more human friendly format than the (reversed) array
DeleteDear Gilles,
ReplyDeleteKindly allow me to use the above code in an article.
I will cite your blog accordingly.
Thank you!