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:

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:

8
0 9 0 3 2 0 0 0
0 0 7 2 0 0 9 0
7 0 0 0 0 7 7 0
0 2 0 0 0 0 0 0
0 0 0 0 0 0 5 0
0 3 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 4 0
9
0 5
3 6
6 4
3 2
5 4
5 3
7 6
4 5
2 6

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! 🙂

def visit_position(list_results,list_visited):
    #returns the position in list_results of the smallest value, which is not visited
    list_smallest = []
    smallest_value = float('inf')
    
    for i in range(0,len(list_visited)):       
        if list_results[i] != float('inf') and list_visited[i] == 0:
            list_smallest.append(i)
            
    for i in range(0, len(list_smallest)):
        if list_results[list_smallest[i]]

Enjoy the code 🙂