查找穿过特定顶点之间的最短路径 [英] Finding shortest path between pass through a specific vertex

问题描述

我有这个问题
给定一个有正向边权重且有界标顶点x的有向图G，您的目标是找到从一个顶点v到穿过该界标的另一个顶点w的最短路径的长度X。

I have this question Given a directed graph G with positive edge weights and a landmark vertex x, your goal is to find the length of the shortest path from one vertex v to another vertex w that passes through the landmark x.

需要描述此问题的O（E log V）算法。
我知道Dijkstra算法的复杂度为O（ElogV）。

It is needed to Describe a O(E log V ) algorithm for the problem. I know that the complexity of Dijkstra Algorithm is O(ElogV).

请帮助我如何开始解决这个问题。

Please can you help me in how to start solving this problem.

推荐答案

如果首先使用Dijkstra算法找到从v到x，p_1和从x到w，p_2的最短路径，然后将它们串联路径p，则这将是从v到w到x的最短路径。

If you first find the shortest path from v to x, p_1 and from x to w, p_2 using Dijkstra's Algorithm and take the concatenation of these paths, p, then this will be the shortest path from v to w through x.

如果存在较短的路径p'，则在x处拆分此路径将产生从v到x，p_1'的路径，以及从x到w，p_2的路径其中p_1'短于p_1，或p_2'短于p_2（否则，长度（p_1'+ p_2'）>长度（p_1 + p_2））是矛盾的。

If there were a shorter path, p', then splitting this path at x would yield a path from v to x, p_1' and one from x to w, p_2' where p_1' is shorter than p_1, or p_2' is shorter than p_2 (otherwise length(p_1'+p_2') > length(p_1+p_2)) which is a contradiction.

编辑：这显然是O（E logV），因为它只是两次使用Dijkstra。

This is obviously O(E logV) since it is just using Dijkstra twice.

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