How do find the longest path in a cyclic Graph between two nodes?

Question

I already solved most the questions posted here, all but the longest path one. I've read the Wikipedia article about longest paths and it seems any easy problem if the graph was acyclic, which mine is not.

How do I solve the problem then? Brute force, by checking all possible paths? How do I even begin to do that?

I know it's going to take A LOT on a Graph with ~18000. But I just want to develop it anyway, cause it's required for the project and I'll just test it and show it to the instructor on a smaller scale graph where the execution time is just a second or two.

At least I did all tasks required and I have a running proof of concept that it works but there's no better way on cyclic graphs. But I don't have clue where to start checking all these paths...

Campstool

On cyclic graphs longest path will be of infinite length, isn't it? You will be just going round and round and round and round ... – Mcneal

Even if I mark the visited nodes so I don't visit them again? That's something I still can't understand why. In my mind, it should be like the Dijkstra algorithm, only "reverse". Like suggested below, but I'm not able to make it work. The algorithm finishes, but the results don't seem correct. – Campstool

Answer 1

The solution is to brute force it. You can do some optimizations to speed it up, some are trivial, some are very complicated. I doubt you can get it to work fast enough for 18 000 nodes on a desktop computer, and even if you can I have no idea how. Here's how the bruteforce works however.

Note: Dijkstra and any of the other shortest path algorithms will NOT work for this problem if you are interested in an exact answer.

Start at a root node *root*
Let D[i] = longest path from node *root* to node i. D[*root*] = 0, and the others are also 0.

void getLongestPath(node, currSum)
{
    if node is visited
        return;
    mark node as visited;

    if D[node] < currSum
        D[node] = currSum;

    for each child i of node do
        getLongestPath(i, currSum + EdgeWeight(i, node));

    mark node as not visited;
}

Let's run it by hand on this graph: 1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)

Let the root be 1. We call getLongestPath(1, 0);
2 is marked as visited and getLongestPath(2, 4); is called
D[2] = 0 < currSum = 4 so D[2] = 4.
3 is marked as visited and getLongestPath(3, 4 + 5); is called
D[3] = 0 < currSum = 9 so D[3] = 9.
4 is marked as visited and getLongestPath(4, 9 + 7); is called
D[4] = 0 < currSum = 16 so D[4] = 16.
5 is marked as visited and getLongestPath(5, 16 + 1000); is called
D[5] = 0 < currSum = 1016 so D[5] = 1016.
getLongestPath(3, 1016 + 200); is called, but node 3 is marked as visited, so nothing happens.
Node 5 has no more child nodes, so the function marks 5 as not visited and backtracks to 4. The backtracking will happen until node 1 is hit, which will end up setting D[3] = 100 and updating more nodes.

Here's how it would look iteratively (not tested, just a basic idea):

Let st be a stack, the rest remains unchanged;
void getLongestPath(root)
{
    st.push(pair(root, 0));

    while st is not empty
    {
        topStack = st.top();
        if topStack.node is visited
            goto end;
        mark topStack.node as visited;

        if D[topStack.node] < topStack.sum
            D[topStack.node = topStack.sum;

        if topStack.node has a remaining child (*)
            st.push(pair(nextchild of topStack.node, topStack.sum + edge cost of topStack.node - nextchild)) 

        end:
        mark topStack.node as not visited
        st.pop();
    }
}

(*) - this is a bit of a problem - you have to keep a pointer to the next child for each node, since it can change between different iterations of the while loop and even reset itself (the pointer resets itself when you pop the topStack.node node off the stack, so make sure to reset it). This is easiest to implement on linked lists, however you should use either int[] lists or vector<int> lists, so as to be able to store the pointers and have random access, because you will need it. You can keep for example next[i] = next child of node i in its adjacency list and update that accordingly. You might have some edge cases and might need to different end: situations: a normal one and one that happens when you visit an already visited node, in which case the pointers don't need to be reset. Maybe move the visited condition before you decide to push something on the stack to avoid this.

See why I said you shouldn't bother? :)

Antipasto

I can't really comment on this as I have to leave, I just came here to see if there was an answer. However, can it be done without recursion in a easy way or just complicates things? I'll check your post with more time in a few hours when I come back from classes. – Campstool

Recursion just means that an implicit stack is maintained in memory, where things like the function arguments and local variables are pushed on for each function call. You can maintain that stack yourself and thus avoid recursion, however I think it only complicates things. Recursion isn't the bottleneck here. You should focus on heuristical optimizations instead (for example, I think you can return if D[node] >= currSum). This is similar to the traveling salesman problem, so you might want to google that and see what others have come up with. – Antipasto

Also, consider using an approximation algorithm. Must you also return the best possible answer, or is something close enough also good? Consider looking into greedy approximation algorithms and genetic algorithms. Genetic algorithms can also get you the best solution if you let them run long enough. – Antipasto

At this point, I really don't care about optimizations, I really don't have time to bother with that. I emailed the instructor and he understand the fact that it takes a while and that's one of those things to be discussed when presenting the project. I talked about recursion, not because of performance, but because I prefer it that way, that's all. Otherwise I'll have to pass quite a few variables with function parameters and I tend to avoid that as it complicates things (at least for me). The rain somewhat stopped, let me see if I can get to class now :X – Campstool

I just implemented the algorithm you posted and: 1) I couldn't mark the root node as visited or it would exit on the first call to getLongestPath; 2) This calculates the longest path from X to all other nodes, I just want to calculate from X to Y, how can I stop it when it reaches there? 3) Also, how do I save the path, the nodes it needs to traverse for that longest path? 4) I would really prefer an iterative algorithm, cloud you post one? I'll probably need to use a queue or stack won't I? But I can't get my head around on how to implement the recursion backtracking iteratively. – Campstool

1) Oops, sorry :). You're right, don't mark the root initially. 2) You can't exactly stop it because you don't know when you have done the final update. Just start from node X and print D[Y]. Dijkstra works the same, it calculates the distances from a starting node to at least some of the other nodes as well. 3) Keep T[x] = the last node that updated the distance to x. For example, add a father parameter to the function. Then, when D[node] < currSum fires set T[node] = father. 4) Yes, you should implement your own stack. It gets very messy, you should really just use recursion IMO. – Antipasto

2) Yes, but I stop Dijkstra when I reach the node I want, I was looking for a similar approach. I don't need to compute all the other distance if I've reached the node I want. 4) I already have a stack implemented, can you give me a few pointers (not like that xkcd joke please) on which changes would I have to do to make the algorithm iterative? If I can't do it in my timeframe, I'll just do it recursively then. But I wanted to try at least, I'm just not sure what to do... – Campstool

2) I hope you know that you can only stop Dijkstra after extracting the destination node from the priority queue and not when first relaxing it. In the worst case, you will have to calculate the distances to all the other nodes as well. In any case, I don't think you can terminate the search prematurely in this situation, only more or less prune the search space. 4) I updated my post with some ideas. – Antipasto

2) I think I'm doing it right lol. But I see what you mean on this situation, I wasn't thinking clearly. 4) Thanks, I'll look into them and see which one I'll use :P – Campstool