Python Algorithms – Full Dijkstra is stunning again

Yesterday I have spent some hours, trying to resolve one problem for shortest paths. The problem was coming from HackBulgaria and was somehow similar to these two problems here:

• Get the shortest path in a weighted graph with Dijkstra
• Dijkstra for all nodes

The “somehow similar” was used by me, because there were some procedures, that I have used from these two articles to resolve my problem. Pretty much, here is the description of the problem:

---

Vitosha Run

You are participating in the first-of-its-kind trail running marathon on Vitosha. You are going to compete against a bunch of trained and skilled runners in running through a square area of the mountain. The uniqueness of this marathon is that each runner can choose his own route. You studied carefully this matter and it turns out that altitude is the main thing to consider.

You have an altitude map of the area, represented by a square matrix. Each cell of the matrix contains the altitude of that part of the terrain. When you are in a given cell, you can run to any of the 8 adjacent cells and this will take one minute + the absolute difference in altitudes between the current cell and the cell you are going to, counted as minutes.

You want to know what is the minimal time in which you can complete the track.

Input: The first line of the input will contain N – the number size of the map. The second line will contain 4 integers RowStart,ColumnStart and RowFinish, ColumnFinish – the zero-based coordinates of the start and the finish on the map. The next N lines will each contain N integers representing the altitude of the corresponding cell in the map.

Output: Output the minimal possible time in which you can run from the start to the finish.

Limits: 1 <= N <= 250

Input:

Output:

---

So, what do we have to do? Calculate the shortest path in a weighted graph of course 🙂

But this time it is more tricky, because we have to calculate the weights by ourselves. Thus, I have came up with an idea to build a matrix which shows the distances from each point to each point. Thus, making the problem a little more complicated, but it was easier for me to make sure that what I was doing was correct. So, first I have decided to build a matrix on pen and paper, giving me the direct distances from a simple matrix like this:

So, if you take a look at the drawing below (it is a masterpiece, I know), on the top right you will see the matrix I am talking about. In it, you will notice that the way from a to b is 2 abs(1-2)+1 and the way from f to b is 5 abs(6-2)+1.

Once, I had something like this in code, probably half of the work would be considered done. Then I would have a simple matrix with positive weights, which is exactly what the Dijkstra algorithm needs.

Thus, in order to build this matrix, I have built the following 4 functions (see them in the code later):

def up_left_exists(matrix,row,col):
def up_right_exists(matrix,row,col):
def up_middle_exists(matrix,row,col):
def same_line_left_exists(matrix,row,col):

Thus, after starting to go one by one for the matrix from 0 to 8, I was able to fill the matrix with the paths. In my code the matrix with the path is called real_matrix and looks like this:

Pretty much it is the same as the one above, initially drawn by me, but it is even mirrored (e.g. you can reach a from b for the same weight as b from a). So, after having the weights the task was a little easier. I had to implement Dijkstra, and although I have done it a few times already and I had the code in front of me, I had some difficulties. Anyway, I have managed to get over them and the results was stunning (at least for me).

So, finally, here comes the code:

Also in GitHub.

Enjoy it!