7
I’m trying to solve this programming problem.
In summary, the problem describes several bus lines as an undirected graph and says that a bus ticket costs 1 real. Can someone give me a hint on how I can get the lowest real cost out of one in A to B ?
I couldn’t think of any strategy using a wide search.
In this example below the lowest value to go from A to B would be 2 real. 1 real with a passage through the red line and the other real by a passage of the blue line.
3
The first thing you should notice in the problem is that the cost between the various bus lines is always 1, then you don’t even need to use the dijkstra’s algorithm or any other generic shortest path algorithm. A simple Search in Width is enough and faster.
The second important point is how to build your graph. By the problem statement you can see that a Campus is connected to X other campuses by a bus line, which you can use indefinitely (as long as you don’t get off the line) to walk between all campuses connected by such a line. What that tells you is: all vertices (the campi) of a bus line have access to all other vertices, that is, they are connected in the graph, with edges of weight 1.
Taking the example input of the problem:
9 4
6 2 3 4 6 7 9
4 1 3 4 5
3 8 3 4
2 9 8
On the second line we have 2 3 4 6 7 9 (we can ignore the 6 here, because it is only used to inform how many vertices are present in the line). All these vertices shown can reach any of the other vertices by paying only a price of 1, then the representation of these connections in an adjacency matrix is as follows:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
--- --- --- --- --- --- --- --- ---
1 | | | | | | | | | |
2 | | | T | T | | T | T | | T |
3 | | T | | T | | T | T | | T |
4 | | T | T | | | T | T | | T |
5 | | | | | | | | | |
6 | | T | T | T | | | T | | T |
7 | | T | T | T | | T | | | T |
8 | | | | | | | | | |
9 | | T | T | T | | T | T | | |
where T indicates that there is an edge connecting two vertices, and the absence of T indicates that it is not possible to reach from one vertex to another (this graph represents only the connections given by the first bus line in the example!).
In short: When reading the input of the problem, build your graph so that all Campi of a line have access to all other Campi of the same line. And run a Width Search on the graph. This will give you the correct answer.
1
Your question does not have a simple answer because this graph problem is not simple.
You must use an algorithm that solves the "Minimum Path Problem" (English: Shortest path problem).
I don’t know which of the two would be faster in your case, so try one of the two:
If you search in English, it would be easier. Example: Dijkstra in Java.
Browser other questions tagged algorithm graph
You are not signed in. Login or sign up in order to post.