问题描述
由于有向图 G =（V，E），两个顶点取值， T 和两个权重函数 W1 ， W2 ，我需要找到最短路径从取值按 W2 所有的最短路径中，以 T 在取值到 T 按 W1 。首先，我怎么能找到两个顶点之间所有的最短路径取值和 T ？ Dijkstra算法可以帮助我们找到最短路径从顶点到其他每个顶点的访问，是有可能对其进行修改，以获得两个顶点之间所有的最短路径？
Given a directed graph G=(V,E), two vertices s, t and two weight functions w1, w2, I need to find the shortest path from s to t by w2 among all the shortest paths between s to t by w1.First of all , how could I find all the shortest paths between two vertices s and t? Dijkstra's algorithm helps us find shortest path from a vertex to to every other accessible vertex, is it possible to modify it in order to get all the shortest paths between two vertices?
推荐答案
我会提出意见的问题展开。的问题是，对于一些图形，可以有最短路径两个顶点之间的指数数，例如
I will expand on comments to the question. The problem is, for some graphs, you can have an exponential number of shortest paths between two vertices, for example
o o o
/ \ / \ / \
u o o o ... o o v
\ / \ / \ /
o o o
下面有 O（2 ^ | V |）的 U 和最短路径 v 。
更好的办法是提出@nm一个在注释：
The better approach would be the one proposed by @n.m. in the comments:
只需使用一个权重函数w =（W1，W2），与组分逐加成和词典式排序。
辞书除了很简单：你定义一个新的权重函数为 W（E）=（W1（E），W2（E））（即矢量的使用给定的2个权重函数）的权重
The lexicographical addition is straightforward: you define a new weight function to be w(e)=(w1(e), w2(e)) (i.e. a vector of the weights using the given two weight functions).
然后定义加法运算（你必须有一个用于权重函数设定目标）：
Then you define the addition operation (you have to have one for a weight function target set):
w = (w1, w2)
W = (W1, W2)
w + W := (w1 + W1, w2 + W2)
有关我们的情况：你必须按权重函数的最短路径 W =（W1，W2）， P0 。让我们证明它会根据 W2 的最短路径中，根据是最短路径 W1 。
For our case: you have a shortest path according to the weight function w = (w1, w2), p0. Let's prove it will be the shortest path according to w2 among the shortest paths according to w1.
基本上，这意味着，每通道 P W（P）＆GT; = W（P0）这意味着要么 W1（P）＆GT; W1（P0）（让 P 不中是最短的，根据 W1 ）或 W1（P）= = W1（P0）和 W2（P）＆GT; = W2（P0）所以路径 P 是众多最短根据 W1 但根据 W2 。这意味着， P0 是最短的，根据 W2 之间的最短根据 W1 。
Basically it means that for every path p w(p) >= w(p0) which means that either w1(p) > w1(p0) (so p is not among the shortest according to w1) or w1(p) == w1(p0) and w2(p) >= w2(p0) so the path p is amongst the shortest according to w1 but it is not shorter according to w2. That means that p0 is the shortest according to w2 amongst the shortest according to w1.
这篇关于找出所有最短两个顶点之间的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！