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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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! 🙂
|
1 2 3 4 5 6 7 8 9 10 11 |
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 🙂