循环图中涉及转移的最短路径问题

Question

我正在尝试解决图形问题：
有(n+1)个城市(0到n号)，(m+1)条公交线路(0到m号)
（一条线可能包含重复的城市，这意味着该线有一个周期。）
每条线路覆盖多个城市，从i城市到j城市需要t_ij到运行（不同线路t_ij可能不同）。 =26=] 而且每次坐公交都要额外transfer_time

边看起来像这样：城市 i --(time)-->city2
示例 1:
n = 2，m = 2，开始 = 0，结束 = 2
第 0 行：
0 --(1)--> 1 --(1)--> 2； transfer_time = 1
第 1 行：
0 --(2)--> 2； transfer_time = 2
Line0取1+1+1 = 3，line1取4，所以min是3.

示例 2:
n = 4，m = 0，开始 = 0，结束 = 4
第 0 行：
0 --(2)--> 1 --(3)--> 2 --(3)-->3 --(3)--> 1 --(2)--> 4； transfer_time = 1
需要1（0点上车）+ 2（从0到1）+ 1（下车上车，换乘）+ 2 = 6

我尝试用 Dijkstra 算法解决它，但未能处理带循环的图形（如示例 2）。下面是我的代码。

struct Edge {
    int len;
    size_t line_no;
};

class Solution {

public:
    Solution() = default;

    //edges[i][j] is a vector, containing ways from city i to j in different lines
    int findNearestWay(vector<vector<vector<Edge>>>& edges, vector<int>& transfer_time, size_t start, size_t end) {
        size_t n = edges.size();
        vector<pair<int, size_t>> distance(n, { INT_MAX / 2, -1 }); //first: len, second: line_no
        distance[start].first = 0;
        vector<bool> visited(n);
        int cur_line = -1;
        for (int i = 0; i < n; ++i) {
            int next_idx = -1;
            //find the nearest city
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && (next_idx == -1 || distance[j].first < distance[next_idx].first))
                    next_idx = j;
            }
            visited[next_idx] = true;
            cur_line = distance[next_idx].second;
            //update distance of other cities
            for (int j = 0; j < n; ++j) {
                for (const Edge& e : edges[next_idx][j]) {
                    int new_len = distance[next_idx].first + e.len;
                    //transfer
                    if (cur_line == -1 || cur_line != e.line_no) {
                        new_len += transfer_time[e.line_no];
                    }
                    if (new_len < distance[j].first) {
                        distance[j].first = new_len;
                        distance[j].second = e.line_no;
                    }
                }
            }
        }

        return distance[end].first == INT_MAX / 2 ? -1 : distance[end].first;
    }
};

有没有更好的练习来解决这个问题？提前致谢。

Answer 1

您的 visited 集看起来不对。您要输入 Djikstra 算法的“节点”不能简单地是城市，因为这不能让您模拟城市内从一条线路切换到另一条线路的成本。每个节点必须是一个对，由一个城市编号和一个公交线路编号组成，代表你当前乘坐的公交线路。公交线路号可以是-1表示你不在公交车上，起点和终点节点的公交线路号都是-1。

然后每条边将代表停留在您当前乘车前往下一个城市的路线上的费用，或在您当前所在城市下车（免费），或上公交线路的费用在您当前所在的城市（有接送费用）。

你说城市编号从 0 到 n 但我看到一堆循环停止在 n - 1（因为他们使用 < n 作为循环条件），所以这可能是另一个问题。

循环图中涉及转移的最短路径问题

Shortest path question involving transfer in cyclic graph

c++

graph

shortest-path