从给定顶点到另一个顶点的有向加权图中最长路径

该图为正加权值，可能是非循环的。从给定顶点到另一个顶点的有向加权图中最长路径

输入文件包含

顶点数目，边数，begining顶点，结束顶点

EDGE1（从，到，重量）

EDGE2（从，到，体重）等上。

的路径的长度将是无限的，如果有循环图形中，将是0，如果没有办法

我的方式是，我除去同一边缘具有较少的长度，并使用贝尔曼福特或dijkstra的算法在双眼列表或矩阵中，并且都可以正常工作。

然而，程序应该找到最多2秒的路径和一些输入文件包含10000个顶点和100000个边

我该怎么办？

来源

2013-12-21 gertlek

要在本网站上获得一些帮助，您应该显示您已有的程序代码，包括编程语言...... – rene

时间限制是2秒，这意味着程序应该有大约10^6次迭代。请参阅V = 10000和e = 100000的限制。这意味着O（V）或O（E）或O（V + E）的算法甚至可以在给定的时间内很容易地计算出您的要求。

Note E + Vlogv ~ (100000 + ~132877) which is less than 10^6

//对于10^9 Hz频率的处理器，这个10^6限制会退出。所以，即使你的算法对每次迭代都有1000条指令，你将会处于安全区域。

所以，这里所提出的算法：

你将建立在O(E)图。使用邻接列表数据结构来表示图形。 - >在构建这个数据结构时，存储每个顶点的indegree并存储顶点数。
```
countV := V; 
foreach edge_i 
    inDegree[to] := inDegree[to] + 1; 
```

检查图中是否有循环O(V + E)。

if no vertex with indegree = 0 and countV = 0 
    graph has no cycle 
else if no vertex with indegree = 0 and countV != 0 
    graph has cycle 
else select any vertex having 0 indegree 
    countV := countV - 1; 
    decrease all its directed neighbours' inDegree by 1.

所以，如果你得到一个循环，你的答案是直接无穷。

做一个BFS或DFS得到ending vertex是来自beginning vertex或无法访问。这可以在O(V + E)或甚至O(E)完成。让我们拿O(V + E)。如果不可以，你的答案是直接0.
现在，应用dijkstra但在放松条件下，只是检查相反。一世。E在伪给出here，而不是做
```
if alt < dist[v]: 
    dist[v] := alt; 
```

做

if alt > dist[v]:         
     dist[v] := alt;

这可以O(E + VlogV)完成。因此解决方案的总体复杂性将是O(E + VlogV)，这在很大程度上受到限制。

来源

2013-12-24 19:02:08

从给定顶点到另一个顶点的有向加权图中最长路径

回答

相关问题