查找图中两个节点之间的路径，根据给定的标准 - 优化任务 [英] Find path between two nodes in graph, according to given criteria - optimization task

问题描述

我有以下问题。我有循环，无向，加权图G =（V，E）。我需要根据这些规则，找到简单的路径（无环）两个给定节点之间：

I have the following problem. I have cyclic, undirected, weighted graph G=(V,E). I need to find the simple path (without cycles) between two given nodes according to these rules:

在边缘设置每一个可能的路径
1. 查找最小重量值
2. 选择这条道路，它有选择最低值之间的最大最小值从找到的路径

1. Finding minimal weight value in edges set of each possible path
2. Select this path, which has maximal min value among selected minimal values from found paths

例如，我们图$ P $下面psented：

E.g we have graph presented below:

我们可以尝试找到从节点1简单的路径节点8.有两种可能pathes，列举如下：

We can try to find simple path from node 1 to node 8. There are two possible pathes, listed below:

1. 1 - > 3 - > 5 - > 8，这条路径上最小的边的权重为2
2. 1 - > 3 - > 5 - > 6 - > 7 - > 8，这条路径上最小的边的权重为283

据presented标准，希望路径是路径2号，因为它具有更大的最小值，比路1号。

According to presented criteria, wanted path is path number 2, because it has greater minimal value, than path no 1.

一个重要的假设：在图中节点的数量是非常小的：小于15

One important assumption: the number of nodes in graph are very small: less than 15.

我想过的Dijkstra或Bellman-Ford算法​​的修改，但面临的挑战是，我们没有地方标准（最小距离） - 我们找不到边最小的重量，直到我们没有得到整个路径。 ..

I thought about Dijkstra or Bellman-Ford algorithm modification, but the challenge is, that we don't have local criteria (the min distance) - we cannot find minimal weight of edge, until we don't obtain whole path...

我的第二个思考是使用最近邻点算法的改进，但它用于解决所谓的旅行商问题，这是比较我的一点点不同的情况。

My second think was to use modification of Nearest-Neighbor algorithm, but it's used for solving so called travelling salesman problem, which is a little different case comparing to mine.

我的问题是以下。它是更好的办法来解决这个问题，不是使用深度优先算法，以获得两个特定节点之间的所有有向无环简单路径和下一个选择每发现路径的最小重量值的最大值？

My question is following. Is it better way to solve this problem, than use Depth-First Algorithm to obtain all direct acyclic simple paths between two given nodes and next select max value of min weight values of each found path?

在这种情况下，我对DFS算法的复杂性有点担心，特别是由于递归和图形可以连接（边）的数量。

In such case I'm a little worried about complexity of DFS algorithm, especially due to recursion and number of possible connections (edges) in graph.

感谢你的任何想法。

推荐答案

使用二进制搜索上最小边重量：

假设你的搜索间隔为 [M，M] 。对于设定值 L =（M + M）/ 2 ，使用的 BFS 或 DFS 找到从<$路径C $ C>源到目标等所有边缘有分量＆GT; = L 。如果你能做到这一点，设置 M = L + 1 和重复搜索。如果你不能做到这一点，设置 M = L - 1 和重复搜索

Assume your search interval is [m, M]. For a set value L = (m + M) / 2, use BFS or DFS to find a path from source to destination such that all edges have weight >= L. If you can do this, set m = L + 1 and repeat the search. If you cannot do this, set M = L - 1 and repeat the search.

这将是 O（（边+节点）登录maxEdgeWeight）。应该是非常快的少数几个节点。

This will be O((edges + nodes) log maxEdgeWeight). Should be very fast for your small number of nodes.

请注意，有一种方法可以做到这一点没有日志因素，以及通过使用的 Dijkstra算法和计数排序。但你绝对不需要这个了这么几个节点。

Note that there is a way to do it without the log factor as well, by using the ideas of Dijkstra's algorithm and counting sort. But you definitely do not need this for so few nodes.

更新1：

下面是如何做到这一点的工作在你的榜样。首先，你的搜索区间为 [2，9000] ，因为这些都是你的最大和最小边权，分别为。

Here is how this would work on your example. First of all, your search interval will be [2, 9000], since these are your min and max edge weights, respectively.

L = (2 + 9000) / 2 = 4501
=> Find a path from 1 to 8 such that all of its edges have weight >= 4501.
   This is not possible, so reduce the search interval to [2, 4500].

L = (2 + 4501) / 2 = 2251
=> Find a path from 1 to 8 such that all of its edges have weight >= 2251.
   This is not possible, reduce the search interval to [2, 2250]

L = (2 + 2250) / 2 = 1126
=> Not possible to find a path, reduce to [2, 1125]

L = (2 + 1125) / 2 = 563
=> Not possible, reduce to [2, 562]

L = (2 + 562) / 2 = 282
=> Success! We can find 1 -> 3 -> 5 -> 6 -> 7 -> 8
Mark 282 as the current best answer, and keep searching in [283, 562].

最后，你将留下 283 的答案，这就是你想要的。然后，只需打印所有边权的任何路径＆GT;。= 283 （只有一个你的情况）

Eventually, you will be left with 283 as the answer, which is what you want. Then just print any path with all edge weights >= 283 (only one in your case).

这篇关于查找图中两个节点之间的路径，根据给定的标准 - 优化任务的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！