两个顶点之间最长的路径 [英] Longest Path between two vertices

问题描述

我有向图，加权边（权重都是积极的）。

I have a directed graph with weighted edges (weights are all positive).

现在，我正在寻找一个高效的算法或code（特别是C＃）找到两个给定顶点之间的最长路径。

Now, I'm looking for an efficient algorithm or code (specifically, C#) to find the longest path between two given vertices.

推荐答案

这是完全等同于所有负权重的最短路径算法。要做到这一点，你需要确认，目前并无任何负面的权重周期（这在原来的情况下，大约相当于核实无阳性重量周期）。最好的办法是采取权重的加法逆和运行贝尔曼 - 福特，再取结果的反加。

This is exactly equivalent to a shortest-path algorithm with all negative weights. To do that, you need to verify that there are no negative-weight cycles (which in your original case is probably equivalent to verifying no positive-weight cycles). Best bet is to take the additive inverse of the weights and run Bellman-Ford, then take the additive inverse of the result.

这篇关于两个顶点之间最长的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！