寻找可能忽略1（最长）边缘的最短路径 [英] Finding the shortest path with possibility of ignoring 1(the longest) edge

问题描述

我想知道是否可以用这种方式修改Dijkstra'a Alghorithm：
假设有两个顶点之间有两条路径，长度如下：

  5,8,6,9 // sum = 28 
 2,4,8,25 // sum = 39 
  

第一条路径较短，但在忽略最长边缘后，我得到以下总和：19和14，所以我选择第二条路径。

也许有不同的解决方法，而不使用Dijkstra？

我不知道这个想法是否有效，但首先我认为它可以。

对于每个访问节点，除了距离 D（n ），存储路径上最长边的长度，比如 L（v）。对于所有邻居<$ $，未访问邻居节点的距离为 min D（n）+ L（n） - max（L（n），weight（v，n）） c $ c> n 被访问。下一个访问节点的 L（v）为 max（L（n），weight（v，n）），如果 n 是到 v 的路径上的最后一个节点。如果有更多的路径到 v （更多 n's ）具有相同的长度，那么选择一个最大的 L（v）。

I was wondering if I can modify Dijkstra’a Alghorithm in this way: Let’s say there are 2 paths between two vertices with following lengths:

5, 8, 6, 9  // sum=28
2, 4, 8, 25 //sum=39

First path is shorter but after ignoring the longest edge in both I get the following sums: 19 and 14, so I choose the second path.

Maybe there is different way to solve it, without using Dijkstra?

解决方案

I'm not sure is this idea working, but on first it seems to me like it can.

For each visited node, beside distance D(n), store length of longest edge on the path to it, say L(v). Distance of unvisited neighbouring node is min D(n) + L(n) - max(L(n), weight(v,n)), for all neighbours n that are visited. L(v) of next visited node is max(L(n), weight(v,n)), if n is last node on a path to the v. If there are more paths to v (more n's) with same length, than choose one with largest L(v).

这篇关于寻找可能忽略1（最长）边缘的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！