let's say I have an undirected unweighted graph where each edge can be "visited" only once. How can I get the longest path? I've seen something like NP-hard or depth-first search. Thanks for help
[Math] Longest path in undirected graph
graph theory
Related Solutions
Consider the following algorithm, where we start at terminal nodes and keep removing them while accounting for the corresponding paths. For each node $v$, we store $2$ longest paths we have obtained so far (say of length $l_1(v)$ and $l_2(v)$, with $l_1 \geq l_2$), which end at that node. Initially set all these values to zero.
- Let $v$ a terminal vertex in the tree and let $(u,v)$ be the edge touching it.
- Set $l = l_1(v) + w(u,v)$.
- Modify $l_1(u)$ and $l_2(u)$ by picking the largest two among $l_1(u)$, $l_2(u)$ and $l$.
- Remove the terminal node $v$ and its edge $(u,v)$ from the tree. If the tree is not empty (no edges), go back to step $1$.
When all edges have been removed, we can show that maximum path length is given by $\max {(l_1(v) + l_2(v))}$, over all nodes $v$ in the original tree. Each vertex and edge is visited exactly once and all the operations are constant time, so the algorithm is linear in the number of vertices.
I assumed here that an empty path (path with no edges) is admissible and has length $0$ (for example, when all edge weights are negative, empty path is the longest). But if you only want non-empty paths, you could change the initialization of $l_1$ and $l_2$ values for all nodes to $-\infty$ instead of $0$.
Your assumption is false, this is a counterexample:
Check, that the longest path (all black edges) has weight $6$, while any path containg the red edge has at most weight $5$.
Best Answer
If there are no cycles in your graph, you can put -1 weights on each edge and search for the shortest path with the Bellman-Ford algorithm.
If there are cycles, your problem is NP-hard indeed, and you need to proceed differently, with integer programming for example.
Note. The shortest path with negative weights equals the longest path. If weights are unitary, and the shortest path is, say -20, then the longest path has length 20.