Maximum profit using Dijkstra Algorithm

问题:

Dijkstra algorithm is one of the fastest algorithm for solving the shortest path problem. In my case network is made up of nodes where the weight of the edge is the profit that I get. I was wondering if I could reverse Dijkstra's algorithm to solve this problem, but I realized what if we run in a closed loop (because cost will increase more and more it will go on forever). I know how to solve it as an integer programing problem so I can verify the correctness of algorithm(and not correct unfortunately). Here is pseudo code for Dijkstra that I have been using. What is correct modification to be done?

ln=∞ for all n∈N∖{s}, ls=0
 N′={s}, N′′=∅
 repeat
     n=argminn′∈N′ln′ N′=N′∖{n}, N′′=N′′∪{n}
     for all (n,m)∈A with m∈N∖N′′ do
         if lm>ln+cn,m then
               lm=ln+cn,m N′=N′∪{m}
         end if 
     end for until (N′=∅ or t∈N′′)

回答1:

This falls under the issue of the Longest Path Problem. In other words, there is no efficient way to find max path (in your case, max profits) in an unweighted graph structure. However, you mentioned that it was a weighted graph, so you might still be able to still do it efficiently if your graph is acyclic:

"A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in −G, then longest paths can also be found in G. For most graphs, this transformation is not useful because it creates cycles of negative length in −G. But if G is a directed acyclic graph, then no negative cycles can be created, and longest paths in G can be found in linear time by applying a linear time algorithm for shortest paths in −G, which is also a directed acyclic graph." as seen in the wiki article.

So, if your graph is acyclic, you can indeed use an efficient algorithm to solve your problem. However, if your graph is not acyclic, then there is no known efficient algorithm.

回答2:

Longest paths in your graphs correspond to shortest paths in the negative graph where all edge weights are negated, so you can use Bellman-Ford to find the longest paths.

Bellman-Ford can also be modified to check if there is a positive cycle: At the end, just do one more iteration. If a node gets relaxed, it's reachable from a positive cycle and you can do a reverse DFS in the longest path tree to find the cycle.

Of course if you want to find a longest simple path (without edge/node repetitions), the problem is NP-hard, as Rocks25 pointed out.