通过 m 条边的最短路径

Question

各位聪明人你好。

我有以下图形问题。

给定一个完整的、有向的、带 n 个顶点的加权图，找到通过 m - 1 条边（路径中的边可能重复）的最短路径（从任何顶点开始）的长度。至于极限n <= 200, m <= 1e9.

看看这些限制，我可以说一定有一些聪明的方法没有某种 dp 和图形遍历，但我只是想不出类似的东西。提前致谢。

Example:
n = 3, m = 5

edges:
1 -> 2 weight = 10,
1 -> 3 weight = 100,
2 -> 1 weight = 10,
2 -> 3 weight = 50,
3 -> 1 weight = 30,
3 -> 2 weight = 70,

answer would be 40 (1 -> 2 -> 1 -> 2 -> 1)

Answer 1

一个天真的解决方案是运行 BFS（breadth-first 搜索）直到第 m^th 级别并保持最小权重和 return它。

但是在问题中它说我们可以多次包含顶点直到它们之间有一条路径，所以现在我们可以执行以下步骤：

计算图中存在的所有循环，我们可以在计算可能的最小权重时重复使用这些循环。

例如：

题中存在一个循环1-->2-->1，长度=3，权重=20，m的值=5，现在我们可以两次使用这条路径，但是如果m为6，那么我们是剩下 1 个节点要包含。

现在我们可以从 1 计算出长度为 l（如果 m=6 则为 1）的最小路径（包括剩余节点），并将其添加到上述权重中。 (我们将 1-->2 =10)

对图中出现的每个循环重复步骤 1 和 2，并保持最小总和。

下面是描述上述解决方案的c++代码（可能不是100%正确，但你会明白基本的想法）

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Edge{
    int src, dest, weight;
};

struct Node{
    int start_vertex, end_vertex, weight, edge_count=0;
};

class Graph{
public: 
    vector<vector<pair<int, int>>> adjList;
    int V;

    Graph(vector<Edge> edges, int V){

        adjList.resize(V+1);
        this->V = V;

        for(Edge edge:edges){
            adjList[edge.src].push_back({edge.dest, edge.weight});
        }
    }
};

int BFS(Graph &g, int m){

    queue<Node> Q;

    vector<Node> cycles;

    // to store min path from vertex i of length j
    vector<vector<int>> dp(g.V+1, vector<int>(g.V+1, INT_MAX));

    for(int i=0; i<=g.V; i++)
        dp[i][0] = 0;

    for(int i=1; i<=g.V; i++){
        Q.push({i, i, 0, 1});
    }

    while(!Q.empty()){
        Node top = Q.front();

        Q.pop();

        if(top.edge_count >= g.V) break;

        int v = top.end_vertex;
        int start_vertex = top.start_vertex;
        int weight = top.weight;
        int edge_count = top.edge_count;

        for(auto x:g.adjList[v]){
            // finding all the cycles
            if(x.first == start_vertex){
                Node n = {start_vertex, v, weight+x.second, edge_count+1};
                cycles.push_back(n);
            }else{
                Q.push({start_vertex, x.first, weight+x.second, edge_count+1});
            }


            if(dp[start_vertex][edge_count] > weight+x.second){
                dp[start_vertex][edge_count] = weight+x.second;
            }
        }
    }

    // finding minimum:
    int min_weight = INT_MAX;

    if(m<=g.V){
        for(int i=1; i<=g.V; i++){
            min_weight = min(min_weight, dp[i][m]);
        }
    }

    // checking all the cycles for  reusability and maintaining min sum
    for(int i=0; i<cycles.size(); i++){

        int sum = cycles[i].weight;

        int length_left_to_cover = m-cycles[i].edge_count;

        sum += length_left_to_cover/(cycles[i].edge_count-1) * cycles[i].weight;

        int vertices_left_to_include = 0;

        if(m-cycles[i].edge_count>0){

            vertices_left_to_include = (m-cycles[i].edge_count)%(cycles[i].edge_count-1);

        }

        min_weight = min(min_weight, sum+dp[cycles[i].start_vertex][vertices_left_to_include]);
    }

    return min_weight;


}

// 1 -> 2 weight = 10,
// 1 -> 3 weight = 100,
// 2 -> 1 weight = 10,
// 2 -> 3 weight = 50,
// 3 -> 1 weight = 30,
// 3 -> 2 weight = 70,

int main(){
    vector<Edge> edges = {
        {1, 2, 10},
        {1, 3, 100},
        {2, 1, 10},
        {2, 3, 50},
        {3, 1, 30},
        {3, 2, 70}
    };

    int V = 3;
    int m = 5;

    Graph g(edges, V);

    cout<<"Min weight: "<<BFS(g, m);
}

输出：

Min weight: 40

通过 m 条边的最短路径

shortest path going through m edges

algorithm

graph

directed-graph

data-structures