- Forum
- General C++ Programming
- Cheapest Path in Graph
Cheapest Path in Graph
Hi everybody,
I have a graph with n x n vertices which are connected like this:
(Example for n = 4):https://gyazo.com/d9391dae4291c7d696ef9b6bffb0a2c5
That means, you can either go diagonally up right, diagonally down right or just right. Each vertex has a certain weight (represented as double). Now I need to find the "cheapest" path from left to right. Neither start nor end are known, which forces me to find the cheapest path from every vertex in column 1 to every vertex in column n and then find the cheapest of the returned paths. I currently use n² depth-first-searches, which obviously takes forever for big n, but guarantees the optimal solution.
My question now is: Is there an algorithm I missed which simplifies this whole task? Or if not, is there a way to optimize my current algorithm?
If asked I'll add my code, but it is not really relevant to my question.
PS: Please bear with me if I ask something stupid as I do not work with graphs this often.
I have a graph with n x n vertices which are connected like this:
(Example for n = 4):https://gyazo.com/d9391dae4291c7d696ef9b6bffb0a2c5
That means, you can either go diagonally up right, diagonally down right or just right. Each vertex has a certain weight (represented as double). Now I need to find the "cheapest" path from left to right. Neither start nor end are known, which forces me to find the cheapest path from every vertex in column 1 to every vertex in column n and then find the cheapest of the returned paths. I currently use n² depth-first-searches, which obviously takes forever for big n, but guarantees the optimal solution.
My question now is: Is there an algorithm I missed which simplifies this whole task? Or if not, is there a way to optimize my current algorithm?
If asked I'll add my code, but it is not really relevant to my question.
PS: Please bear with me if I ask something stupid as I do not work with graphs this often.
Last edited on
this is one of life's great unsolvable problems. There is no know non-brute force solution.
http://mathworld.wolfram.com/HamiltonianCycle.html
The best solution I came up with on my own is to run the 'greedy algorithm' repeatedly starting it once at each graph node. The best of those solutions is the best answer I ever got without doing the full brute force check. There are all kinds of other algorithms out there for this problem, that one is mine :)
A book I once read said "there is no such thing as the fastest code". The idea being that someone else always seems to find a better way as soon as you claim you have nailed it. That aside, I am sure we could optimize it more. I always do these sorts of things in vectors, not real graph constructs. Chasing pointers is slow. Array indices are fast. I solved this thing in a single line formula in excel once :) that one ran fast also, but that was before excel got chugged up and slow. That algorithm was... sort all the connections from cheapest cost to highest, then peel off that list appropriate connections that did not go somewhere that was already hit. N log n to sort & N to peel. Pretty fast...
http://mathworld.wolfram.com/HamiltonianCycle.html
The best solution I came up with on my own is to run the 'greedy algorithm' repeatedly starting it once at each graph node. The best of those solutions is the best answer I ever got without doing the full brute force check. There are all kinds of other algorithms out there for this problem, that one is mine :)
A book I once read said "there is no such thing as the fastest code". The idea being that someone else always seems to find a better way as soon as you claim you have nailed it. That aside, I am sure we could optimize it more. I always do these sorts of things in vectors, not real graph constructs. Chasing pointers is slow. Array indices are fast. I solved this thing in a single line formula in excel once :) that one ran fast also, but that was before excel got chugged up and slow. That algorithm was... sort all the connections from cheapest cost to highest, then peel off that list appropriate connections that did not go somewhere that was already hit. N log n to sort & N to peel. Pretty fast...
Last edited on
| this is one of life's great unsolvable problems. There is no know non-brute force solution. |
Thought so, but as I usually don't work with a graph I thought might have missed an algorithm ;). Furthermore one of my classmates claimed to have an algorithm which effectively solves that problem for n> 1000, which is another reason I thought I missed an algorithm. He probably just used a greed algorithm as well.
| The best solution I came up with on my own is to run the 'greedy algorithm' repeatedly starting it once at each graph node. |
Well I wouldn't need to start it at every graph node (even though that doesn't matter as I'll have n² depth-first-searches anyways), but since it's a requirement to return the optimal solution I can't use greedy algorithms...
| N log n to sort & N to peel. Pretty fast... |
That is indeed pretty fast.
| I always do these sorts of things in vectors, not real graph constructs |
I actually just defined a custom class "Vertex" which holds the weight, vertices which can be reached from this vertex as well as the vertex used to get to this one. These vertices are then stored in a 2d vector.
Wait a minute...
| http://mathworld.wolfram.com/HamiltonianCycle.html |
What's the Hamiltonian Cycle for? I do not need to visit every vertex exactly once, I need to find the cheapest way from left to right. Is a Hamiltonian Cycle of any use for that?
Last edited on
It isn't an Hamiltonian cycle. That's when you must visit each vertex exactly once. This is "shortest path" which can be done pretty quick.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
A question: do you have to go left to right or can you go right to left also? Put another way, do those edges just go left to right, or can they go right to left too?
If it's left to right only then it's easy to solve. Start by figuring the cheapest way to get from the 3rd column to the 4th. For each node in the 3rd column, record both the edge that's cheapest and the total cost of the path.
Now go to the 2nd column and compute the cheapest path. For each node in the 2nd column, look at the nodes in the 3rd column that it can reach and choose the path with the least total cost. The key here is that you don't have to look at the 4th column, only the 3rd. Again, record the TOTAL cost and the path. Note that for the path, you only have to record the edge to the 3rd column, not the whole path to the 4th column. To reconstruct the path, you just go to that node in the 3rd column and get the edge for it's cheapest path.
Now, do the same for the 1st column: get the cheapest path from each node in the 1st column.
Finally, compare the total cost of each node in the 1st column to find the one with the cheapest path.
This is the same as Dijkstra's algorithm with the small change that you know ahead of time which nodes you to examine when.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
A question: do you have to go left to right or can you go right to left also? Put another way, do those edges just go left to right, or can they go right to left too?
If it's left to right only then it's easy to solve. Start by figuring the cheapest way to get from the 3rd column to the 4th. For each node in the 3rd column, record both the edge that's cheapest and the total cost of the path.
Now go to the 2nd column and compute the cheapest path. For each node in the 2nd column, look at the nodes in the 3rd column that it can reach and choose the path with the least total cost. The key here is that you don't have to look at the 4th column, only the 3rd. Again, record the TOTAL cost and the path. Note that for the path, you only have to record the edge to the 3rd column, not the whole path to the 4th column. To reconstruct the path, you just go to that node in the 3rd column and get the edge for it's cheapest path.
Now, do the same for the 1st column: get the cheapest path from each node in the 1st column.
Finally, compare the total cost of each node in the 1st column to find the one with the cheapest path.
This is the same as Dijkstra's algorithm with the small change that you know ahead of time which nodes you to examine when.
doh! sorry, misread the problem big time!
There are a few practical applications of the cycle but most are contrived. Its more of a brain teaser than a useful construct; the bulk of places where it is needed at all can largely get away with suboptimal solutions that can be found faster.
the one you are doing is much, much more useful.
There are a few practical applications of the cycle but most are contrived. Its more of a brain teaser than a useful construct; the bulk of places where it is needed at all can largely get away with suboptimal solutions that can be found faster.
the one you are doing is much, much more useful.
Last edited on
| A question: do you have to go left to right or can you go right to left also? Put another way, do those edges just go left to right, or can they go right to left too? |
Yes, those edges just go from left to right.
| If it's left to right only then it's easy to solve. Start by [...] |
Interesting algorithm, I'll try to implement it right away, thanks!
| doh! sorry, misread the problem big time! |
No problem, I was just a bit confused why I should compute a Hamiltonian Circle ;).
Last edited on
Hey everybody,
just stopping by to tell you that the implementation of the slightly modified Dijkstra's algorithm works like a charm! Thank you very much for helping me out. One last question concerning the runtime:
The runtime is roughly O(3n * n-1), isnt it? As I have to visit every adjacent node of every node except the ones in the nth column,right?
just stopping by to tell you that the implementation of the slightly modified Dijkstra's algorithm works like a charm! Thank you very much for helping me out. One last question concerning the runtime:
The runtime is roughly O(3n * n-1), isnt it? As I have to visit every adjacent node of every node except the ones in the nth column,right?
Last edited on
It depends on what N is: the number of nodes? The number of columns? It also depends on how the problem expands when N gets bigger: do you simply add more columns of 4 nodes, or does the grid grow to 5x5, 6x6, ... NxN?
| It depends on what N is: the number of nodes? The number of columns? It also depends on how the problem expands when N gets bigger: do you simply add more columns of 4 nodes, or does the grid grow to 5x5, 6x6, ... NxN? |
Ah yes, makes sense.
N is the number of nodes in one column of an NxN grid.
I thought that for a 4x4 grid I'd check 4 nodes per row, each of which is connected to 3 nodes in the 4th column ( well except the first and the last node, which are only connected to 2 other nodes), so roughly 4x3 checks. This is done for columns 3, 2 and 1 - so in total 3 (4-1 as the last row isn't being checked at all) times, resulting in (3x4) x 3 checks. Is this correct?
Last edited on
| That sounds reasonable. Now can you express that for an NxN grid? |
Wouldn't that be (3xn) x (n-1) -> 3n * (n-1)?
Topic archived. No new replies allowed.