Python – Dijkstra algorithm for all nodes

In this article I will present the solution of a problem for finding the shortest path on a weighted graph, using the Dijkstra algorithm for all nodes. The problem is formulated by HackBulgaria here.

Pretty much, you are given a matrix with values, connecting nodes. If a value is zero, no connection is present between the values. The matrix on first picture can be translated to the graph on the second:

matrix   graph

Thus, our target is to find the shortest path in value between any two given points. E.g., let’s say that someone wants to travel from point 0 to point 1. The result should be 5, because travelling from 0 to 3 and then to 1 is 3+2, which is cheaper than the direct travelling to 1.

Thus our input looks like this:

The first line gives the dimensions of the matrix (in our case 8 x 8), the next n lines are lines of the matrix. Then after the matrix we get a number, telling us how many questions from point to point we should have to answer. In our case, we have to answer 9 questions.

What I did? Pretty much, I have calculated all the possible routes between two paths and I have kept them in a list. In the code, this is called list_total_results. Once this is done, I simply access the list to answer a query for the asked path. I have one function in the code (actually it is pretty messy, but it is probably quite ok for 60 lines of code. The function visit_position(list_results, list_visited) is crucial – it takes the list_results and returns the position of the smallest value in it, which has 0 in list_visited. 

Pretty much that is all. It works well and it is Dijkstra implemented by me, without looking at sites and books! 🙂

Enjoy the code 🙂

Tagged with: , , ,