我需要知道是否有可能在任何加权无向图中找到具有最大成本的简单路径.
我的意思是为任何一对顶点找到所有最昂贵的路径.
输入:图G =(V,E)
输出:图G中最昂贵路径的成本.
这个问题NP完全吗？我认为是.你能否提供一篇我可以查看的文章的参考.
你不是第一个想到这个问题的人.事实上,这是谷歌搜索结果中的第一个链接.
编辑
伙计,非加权图是加权图的一个特例:所有边都有权重1 :)
| 归档时间： |
|
| 查看次数： |
1712 次 |
| 最近记录： |