Link to pdf version on UVa OJ
The problem asks us to find the shortest path from source to destination with at most maxStop+1 edges. If you have read about Bellman-Ford algorithm this must not be unfamiliar for you.
In Bellman-Ford algorithm there is a main loop that iterates n-1 times (n being the number of nodes).
At i-th iteration those nodes that their shortest path from source to them consists of i intermediate nodes is fixed, the same thing we want here.
We need to customize Bellman-Ford algorithm and relax Edges maxStop+1 times, instead of n-1 times.
I tried to write the code using a class and some functions.
This is how my main function looks like :
I have a class Graph that inputs the graph and answers the queries for that graph. In terms of clean code and separation of concern, there is at least one problem with this code. Class Graph gets input from standard input like this :
the problem is that if we want to change source of input (let's say instead of standard input, we want to generate random graph, or we want to analyze a picture and generate the graph from that picture), then this Graph class won't be usable. We have hard-coded source of input in this class.
I have a solve() function which it's responsibility is to read input and prepare the graph, then reads queries and uses another function calculateMinDistance() to find the answer for that query.
About 20 lines of code, not that hard to follow what is happening!
I have some data structures in my class, of which the most important one is cityIndex, which is a map of string to ints. Whenever I have a graph that it's nodes are strings, I convert them to integers and work with them.
I use this function to map a string to integer, if it is in the map I return it's index, otherwise I map the size of my map to this city and then return that.
For more details look at my code on github.
The problem asks us to find the shortest path from source to destination with at most maxStop+1 edges. If you have read about Bellman-Ford algorithm this must not be unfamiliar for you.
In Bellman-Ford algorithm there is a main loop that iterates n-1 times (n being the number of nodes).
At i-th iteration those nodes that their shortest path from source to them consists of i intermediate nodes is fixed, the same thing we want here.
We need to customize Bellman-Ford algorithm and relax Edges maxStop+1 times, instead of n-1 times.
I tried to write the code using a class and some functions.
This is how my main function looks like :
I have a class Graph that inputs the graph and answers the queries for that graph. In terms of clean code and separation of concern, there is at least one problem with this code. Class Graph gets input from standard input like this :
the problem is that if we want to change source of input (let's say instead of standard input, we want to generate random graph, or we want to analyze a picture and generate the graph from that picture), then this Graph class won't be usable. We have hard-coded source of input in this class.
I have a solve() function which it's responsibility is to read input and prepare the graph, then reads queries and uses another function calculateMinDistance() to find the answer for that query.
About 20 lines of code, not that hard to follow what is happening!
I have some data structures in my class, of which the most important one is cityIndex, which is a map of string to ints. Whenever I have a graph that it's nodes are strings, I convert them to integers and work with them.
I use this function to map a string to integer, if it is in the map I return it's index, otherwise I map the size of my map to this city and then return that.
For more details look at my code on github.
No comments:
Post a Comment