图中节点之间的最短路径

Question

图中节点之间的最短路径

algorithmdata-structuresgraphdijkstra

4

我不确定是否应该在这里提出这个问题，这个问题与算法有关。想象一下你有一个无向图。边有不同的值。想象一些顶点是“好”的，一些是“坏”的。现在我想确定两个好节点，使它们之间的路径尽可能短（如果路径包括坏节点，那也没问题）。

- Giorgi Cercvadze

Dijkstra算法从单个节点到每个其他节点找到最短路径。因此，您只需要为每个好的节点运行Dijkstra算法。 - user3386109

考虑过这个问题，但是不行，因为有10^6个节点，对每一对节点都进行操作将会花费一辈子的时间。 - Giorgi Cercvadze

1

一种优化方法是跟踪到目前为止的最佳路径，并在所有路径长度超过最佳路径时提前停止算法。这就是“分支定界法”的概念。 - user3386109

是否有原始问题描述及其约束条件的链接？ - juvian

1

我同意@user3386109的观点；你将有两个限制来停止算法：1）如果你到达一个好的节点，你不会将其传递给另一个节点。2）如果路径超过了迄今为止记录的最佳路径。更新最佳记录路径将使你的搜索每一步都最小化。 - Bassem Akl

显示剩余2条评论

2个回答

0

一种方法是添加一个源节点，该节点与每个好节点具有定向连接（权重为0）。

然后运行Dijkstra算法，找到从源节点到每个其他节点的最短路径。

在运行Dijkstra算法时，还要跟踪哪个好节点最接近。

然后对A->B边进行最终遍历，找到“从A到好节点的距离”+“边的权重”+“从B到好节点的距离”的最便宜值，仅包括最接近A的好节点不等于最接近B的好节点的边。

- Peter de Rivaz

你不能在达到另一个好的节点（第一跳之后）就停止吗？OP似乎不关心两个良好节点之间单一最短距离以外的任何事情。 - Ian Mercer

@IanMercer 可能是这样 - 我担心路径可能会回到它开始的好节点，但也许有一种方法可以确保这种情况不会发生？ - Peter de Rivaz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

你需要做的是同时从所有好节点开始生长路径，然后在发现两个节点相遇后立即停止。这样，你就找到了最短路径。

有一个微妙的复杂性。考虑一个三角形ABC。如果A-B和B-C的权重都为2，而A-C为3，则在查看A-C之前，你会先查看A-B和B-C。这意味着你会在查找A-C（权重为3）之前找到路径A-B-C（权重为4）。但是，在所有这样的情况中，你都会在找到第一条边之前看到该边存在。

以下是伪代码。

node_path_info is is a dictionary of vertex to information about the path
upcoming is priority queue of vertices to consider next, sorted on .cost

initialize node_path_info and upcoming
for node in list of good nodes:
    upcoming.add( {
        "node": node,
        "node_from": None,
        "cost": 0,
        "good_node", node,
    } )

best_path_cost = None
best_middle1 = None
best_middle2 = None
while upcoming:
    current = upcoming.pop()
    if current.node in good_node_from:
        if current.good_node == good_node_from[current.node]:
            pass # We found a loop
        else:
            cost = current.cost + node_path_info[current.node].cost
            if best_path_cost is None or cost < best_path_cost < best_path_cost:
                best_path_cost = cost
                best_middle1 = current.node
                best_middle1 = current.node_from
    else:
        node_path_info[current.node] = current
        if best_path_cost is not None: # still looking for first path
            for (next_node, weight) in get_connected_weight(current.node):
                upcoming.add({
                    "node": next_node,
                    "node_from": current.node,
                    "cost": current.cost + weight,
                    "good_node", current.good_node,
                })

path1 = path from best_middle1 back
path2 = path from best_middle2 back
path1 + reversed(path2) is your answer.

在最坏的情况下，您需要两次访问所有边。对于一个随机的连通图和2个好节点，您将访问与O(sqrt(n))个顶点相连的所有边。