data-structures - 寻求为无向加权图添加虚拟节点的示例代码

Question

我知道您应该添加虚拟节点以在任何图中使用 BFS 找到任何 2 个节点之间的最短路径。但问题是我无法理解如何编码。有人可以给我一个例子吗？

标签： data-structures

Answer 1

假设您正在使用邻接列表表示。

假设您当前n在图中有节点。考虑一条边a - b，让它有重量x。因此，为了表示这一点，您需要x-1图表中的虚拟节点。这就是我将如何做到这一点。我假设节点的编号从0 to n.

int dummy_node_count = 0;
for(int i = 0; i < number_of_edges; i++){
    int a,b, cost;
    scanf("%d %d %d",&a,&b,&cost);
    int prev_node = a;

    for(int j = 0; j < cost-1; j++){
        adj_list[prev_node].push_back(n+dummy_node_count);
        adj_list[n+dummy_node_count].push_back(prev_node);
        prev_node = n+dummy_node_count;
        dummy_node_count++;
    }
}
bfs(source, destination);

但是你真的应该使用 Dijkstra 算法在无向加权节点中寻找最短路径。如果成本可以高达 10 ⁸这个解决方案是不可行的。