DEV Community

Cover image for Dijkstra's algorithm in python: algorithms for beginners

Dijkstra's algorithm in python: algorithms for beginners

Maria Boldyreva on July 10, 2018

Photo by Ishan @seefromthesky on Unsplash Dijkstra's algorithm can find for you the shortest path between two nodes on a graph. It's a must-know f...
Collapse
 
nataliaalshevskaya profile image
Natalia Alshevskaya

This next could be written little bit shorter:

path, current_vertex = deque(), dest
while previous_vertices[current_vertex] is not None:
path.appendleft(current_vertex)
current_vertex = previous_vertices[current_vertex]
if path:
path.appendleft(current_vertex)

----->>>

path, current_vertex = deque(), dest
while current_vertex:
path.appendleft(current_vertex)
current_vertex = previous_vertices[current_vertex]

Collapse
 
phlash profile image
Phil Ashby

Nicely done!

If you are only trying to get from A to B in a graph... then the A* algorithm usually performs slightly better: en.wikipedia.org/wiki/A*_search_al... That's what many SatNav packages use :)

Collapse
 
mxl profile image
Maria Boldyreva

Yep! I will write about it soon. Thanks for reading :)

Collapse
 
mistertellini profile image
Aitor López

Hello Maria,

First of all, thank you for taking the time to share your knowledge with all of us! I am sure that your code will be of much use to many people, me amongst them!

I actually have two questions.

First: do you know -or do you have heard of- how to change the weights of your graph after each movement?
In my case, I would like to impede my graph to move through certain edges setting them to 'Inf' in each iteration (later, I would remove these 'Inf' values and set them to other ones.

Second: Do you know how to include restrictions to Dijkstra, so that the path between certain vertices goes through a fixed number of edges?

Many thanks in advance, and best regards!

Collapse
 
mistertellini profile image
Aitor López

Hello back,

I was finally able to find a solution to change the weights dynamically during the search process, however, I am still not sure about how to impose the condition of having a path of length >= N, being N the number of traversed edges. The only idea I have come up with would consist on turning to infinity the last edge towards my destination vertex if the overall distance lies below N. However, this would make this edge no longer available for use for the other paths that would arrive to destination vertex. Any ideas from your side folks? Many thanks in advance, and best regards!

Collapse
 
nick9951 profile image
nick9951

If we want to know the shortest path and total length at the same time
how to change the code?

Collapse
 
ruidazeng profile image
Ruida Zeng

Using Python object-oriented knowledge, I made the following modification to the dijkstra method:

return the distance between the nodes

    distance_between_nodes = 0
    for index in range(1, len(path)):
        for thing in self.edges:
            if thing.start == path[index - 1] and thing.end == path[index]:
                distance_between_nodes += thing.cost
    return distance_between_nodes       
    # return path
Collapse
 
buecktobias profile image
buecktobias

I'd like to know that too.

Collapse
 
neogeomat profile image
neogeomat

The algotithm says

6 Stop, if the destination node has been visited.

in the code

6. Stop, if the smallest distance

among the unvisited nodes is infinity.

if distances[current_vertex] == inf:
break

The code visits all nodes even after the destination has been visited.

Collapse
 
saumitabose62 profile image
Soumita Bose

What changes should i do if i dont want to use the deque() data structure?
Also how to read the graph contents from a file with the below structure
a / b / 3
a / c / 5
...
Source node: a
Destination node: j

Collapse
 
ruidazeng profile image
Ruida Zeng • Edited

Using Python object-oriented knowledge, I made the following modification to the dijkstra method to make it return the distance instead of the path as a deque object.

return the distance between the nodes
distance_between_nodes = 0
for index in range(1, len(path)):
for thing in self.edges:
if thing.start == path[index - 1] and thing.end == path[index]:
distance_between_nodes += thing.cost
return distance_between_nodes

# return path

Collapse
 
saumitabose62 profile image
Soumita Bose

What changes should i do if i dont want to use the deque() data structure?
Also how to read the graph contents from a file with the below structure
a / b / 3
a / c / 5
...
Source node: a
Destination node: j

Collapse
 
ronozoro profile image
Mostafa Mohamed • Edited

This algorithm is working correctly only if the graph is directed,but if the graph is undireted it will not.

To make the algorithm work as directed graph you will have to edit neighbour function as

@property
def neighbours(self):
    neighbours = {vertex: set() for vertex in self.vertices}
    for edge in self.edges:
        neighbours[edge.start].add((edge.end, edge.cost))
        neighbours[edge.end].add((edge.start, edge.cost))
    return neighbours
Collapse
 
abdurrahmaanj profile image
Abdur-Rahmaan Janhangeer

for beginners? sure it's packed with 'advanced' py features. @submit, namedtuple, list comprehentions, you name it!

Collapse
 
kusokmipt profile image
Aleksey Podkidyshev

Can you please tell us what the asymptote is in this algorithm and why?

Collapse
 
davcastroruiz profile image
David Castro

Thank you Maria, this is exactly was I looking for... a good code with a good explanation to understand better this algorithm.

Collapse
 
nolfonzo profile image
nolfonzo

A similar approach here:

rebrained.com/?p=392