图中节点之间的最短路径

Question

我不知道我是否应该在这里问这个问题，问题是关于算法的。假设您有一个无向图。边具有不同的值。假设一些顶点是 "good"，一些是 "bad"。现在我想确定两个好节点，以便它们之间的路径尽可能短（如果路径包括坏节点，那不是问题）。

Answer 1

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

然后运行Dijkstra算法寻找从源节点到所有其他节点的最短路径。

在运行ning Dijkstra 算法的同时，还要跟踪最近的好节点。

然后对边 A->B 进行最后一次遍历以找到 "distance to good node from A" + "weight of edge" + "distance to good node from B" 的最便宜值，仅包括距离最近的好节点的边A不等于离B最近的好节点。

Answer 2

你想要做的是从所有好的节点开始一次增长路径，然后在你发现两个相遇后不久停止。那么你找到了你的最短路径。

有一个微妙的并发症。考虑一个三角形 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)) 个顶点的所有边。

图中节点之间的最短路径

The shortest path between nodes in graph

algorithm

graph

dijkstra

data-structures