练习:
在无向图中,除了边的权重之外,顶点还可以有权重。
这个问题是编写算法,找到图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 的正确性就足够了吗?
有向图的方法是正确的。在原始图中,从一个城市到下一个城市的旅行相关成本由边缘成本和目标城市成本组成。因此,如果您将这些成本合并在有向边中,并删除顶点成本的概念,则您将具有相同的旅行成本,因此 Dijkstra 算法的解决方案也将是您原始图所需的解决方案。
创建此派生图的时间复杂度等于 O(𝑉+𝐸),因为必须创建所有顶点和所有边,并且计算每条边的成本所需的时间是恒定的。这个时间复杂度优于 Dijkstra 算法的时间复杂度,因此图构建步骤不会对其产生负面影响。