时间戳

首页 > 解决方案 > 将图链接到自身的副本并运行约束 dijkstra C++

c++ - 将图链接到自身的副本并运行约束 dijkstra C++

问题描述

我问了一个关于 Dijkstra 的复制策略的问题，我正在尝试编写一个类似于这个答案的程序，在这种情况下，有向加权图 G = (V, E) 包含 0 或 1 的权重。使用复制策略我需要使用 Dijkstra 算法来找到一条至少有 1 条边权重为 0 且边数最少且权重为 1 的路径。

我的问题是我正在使用邻接列表执行此操作，其中 adj[u][v] 包含边缘 U->V 的权重。我知道我需要有 2 个图副本，以便我可以将权重为 0 的边从 G 连接到 G'，并且我使用向量复制构造函数制作了整个图的副本，但我已经达到了我的地步不知道如何连接列表以显示一条边将一个图的顶点连接到另一个图的顶点，以便 Dijkstra 算法在检查边时可以从一个图移动到另一个。

标签： c++algorithmgraphdijkstra

解决方案

您应该构建一个新图，该图按照 trincot 在上一篇文章中对您的回答中描述的方式构建，并且仅在此单个图上工作。这使得 dijkstra 更容易实现，因为您必须处理“转到其他图”的情况。

因此，您基本上将图形复制了 3 次，但每次都将顶点重命名略有不同。通过这种方式，您可以轻松地在这个新图表中添加链接。

for(auto vertex : graph){
    // init newgraph[vertex]
    for(auto edge : vertex){
        // edge is just the other vertex of this edge
        newgraph[vertex].push_back(edge); //just copy
        newcosts[vertex][edge] = costs[vertex][edge]; // just copy
    }
    if(colorof(vertex) == "red")
        newgraph[vertex].push_back(vertex + "_");
        newcosts[vertex][edge + "_"] = 0;
}
for(auto vertex : graph){
    // init newgraph[vertex+"_"]
    for(auto edge : vertex){
        newgraph[vertex + "_" ].push_back(edge + "_" ); //just copy
        newcosts[vertex + "_" ][edge + "_" ] = costs[vertex][edge]; // just copy
    }
    if(colorof(vertex) == "blue")
        newgraph[vertex + "_" ].push_back(vertex + "__");
        newcosts[vertex + "__"][edge] = 0;
}
for(auto vertex : graph){
    // init newgraph[vertex+"_"]
    for(auto edge : vertex){
        newgraph[vertex + "__" ].push_back(edge + "__" ); //just copy
        newcosts[vertex + "__" ][edge + "__" ] = costs[vertex][edge]; // just copy
    }
}

其中graph包含您的图表，costs[a][b]包含从顶点a到的成本b。我使用字符串作为顶点的名称以使命名更容易，如果您愿意，可以将它们存储在地图中，或者使用整数和向量以获得更高的速度。

对于dijkstra，除了每个顶点的正常路径长度之外，您还必须将长度存储在“中间”图中。您以相同的方式执行此操作，但是当两个顶点都在“中间”图形中时，您只会增加长度。当中间图的条件为真时，您只更新顶点。

推荐阅读