练习:
在无向图中,除了边的权重之外,顶点还可以有权重。
这个问题是编写算法,找到图G中顶点a和b之间最便宜的路径。
路径的成本是边的成本之和以及路径上遇到的顶点。
为了更容易理解,我们将其视为:顶点是一座城市,边是城市之间的道路。
我们可以这样考虑权重:
顶点的权重是进入城市之前在红绿灯处的等待时间,边权重是到达该红绿灯的时间(如果有的话)。
我的第一种方法是将每个顶点的权重添加到其连接的所有边上,然后运行 dijkstra,但这是错误的,例如: 图形图像 ,您可以看到从“红色城市”到“绿色城市”的最短路径" 是较低的路径(成本为 11)
,但如果我们使用这种方法,那么我们将得到这个新图,其中最短路径是较高的路径。我认为可行的第二种方法是创建新图,因此对于原始图中的每个无向边 (u,v),在我们创建的新图中添加两条边: (u,v) 使得 w'(u, v)=w(v) 和 (v,u) 使得 w'(v,u)=w(u)。然后我们得到有向图,我们可以在它上面运行 dijkstra。如果我们看一下之前的例子,我们会得到这个图
它是否正确?有没有更简单的解决方案?
至于根据维基百科的时间复杂度,当使用斐波那契堆(我还没学过)时,总成本为 O(E+V log V),但是构建有向图的时间复杂度是多少?如果我想证明\证明正确性,只说因为 dijkstra 的正确性就足够了吗?