使用Dijkstra算法获得最大利润 [英] Maximum profit using Dijkstra Algorithm

问题描述

Dijkstra算法是解决最短路径问题的最快算法之一.在我的情况下，网络由节点组成，其中边的权重就是我获得的利润.我想知道是否可以逆转Dijkstra的算法来解决此问题，但是我意识到如果我们在闭环中运行(因为成本会越来越高，它将永远持续下去)，那该怎么办.我知道如何将其作为整数编程问题来解决，因此我可以验证算法的正确性(不幸的是不能正确地进行校正).这是我一直在使用的Dijkstra的伪代码.正确的修改是什么?

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′′)

推荐答案

这属于最长的问题路径问题.换句话说，没有有效的方法来找到未加权图结构中的最大路径(在您的情况下为最大利润). 但是，您提到这是一个加权图，所以如果图是非循环的，您仍然可以仍然有效地进行操作:

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:

加权图G中两个给定顶点s和t之间的最长路径与通过改变每个权重对其取负而从G得出的图-G中的最短路径相同.因此，如果最短可以在-G中找到路径，然后在G中也可以找到最长路径.对于大多数图形，此变换没有用，因为它在-G中创建了负长度的循环.但是，如果G是一个有向无环图，则不能创建负周期，并且通过对-G中的最短路径应用线性时间算法，可以在线性时间中找到G中的最长路径，这也是有向无环图." 如在 Wiki文章中可以看到.

"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.

这篇关于使用Dijkstra算法获得最大利润的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！