Today, I will take a look at a problem, similar to the one here. In the article there, I produced a matrix, calculating the cheapest plane tickets between any two airports given. Today, the task is a little different. I would calculate the price only between two airports, but I would also show the path between these two. Thus, the task is a little bit more difficult and I am upgrading skills (:
Anyhow, this is how the task originally looks like:
You are out in a foreign city and you want to get to the central station but unfortunately, you figure out that Google Maps does not work offline and data roaming is too expensive to enable.
Fortunately, you have your laptop with you and you downloaded the map data of the city last night in the hotel. Now all you need to do is write a program which will find the shortest path to the station for you.
The map data contains information about junctions, in the form of numbers 1 through N, and streets in the form of triples (i, j, w) – indicating that there is a street between i and j which is w meters long.
You can walk in any direction on the streets.
Write a program which will output the shortest path to the central station, given your current location.
Input
The first line of the input will contain N – the number junctions and M – the number of streets, S – your current location and C – the location of the central station. Each of the following M lines will contain three integers i j w – indicating there is a street between i and j which is w meters long.
Output
On the first line of the standard output, print a single integer – the total length of the route. On the second line, print space separated the indices of the junctions you have to go through.
So, as you probably would expect, the first thing for me to do was to build a picture of the streets with their weights. It looks like this:
Due to the fact, that I was dealing with indices in my lists, I have added the small numbers of indices to the nodes. And the 1 and 8 are covered, because these two nodes were used initially as an example. The arrows show the fastest way from 1 to 8. Pretty much, that is it! Let’s say a few words about the code now 🙂
First, I have built the code, using the previous example here, just adding a traceability option and making a partial Dijkstra only between the nodes I was interested in. In order to track the path, I used a list called list_total_coming_from. In the list, I have used an interesting method to track from which position I was coming to which (at least interesting for me, because I have never seen anyone using something like this) – the value of each index was the position index to which we have come to this value. E.g., for the beautiful painting above, we used to have the following list:
This means, that for the last position (8 in my pic), we have come from node 5. From the position before (7 in my pic), we have come from node 6. The starting position is with -1. Once we have this list, building our way from it is quite easy:
|
1 2 3 4 5 6 7 |
# we need -2, because we finish at -1 and we remove 1 from the answer (-1-1=-2) while(start_from != -2): start_from = list_total_coming_from[start_from]-1 if start_from != -2: result_to_display.append(start_from+1) print(result_to_display[::-1]) #cheap reversing in python :) |
Yup! Finally the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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]] |