问题

LeetCode #787

在单源最短路径问题的基础上,加一条限制,最多只能通过K个点中转,或说最多只能通过K+1条边。

解决

除了Dijkstra之外,还有一个单源最短路径算法,叫做Bellman-Ford算法。离散教材上用它来解决带有负权边的单源最短路径问题。事实上,它也可以解决这种限制了最多中转次数的问题。

Bellman-Ford算法的原型在此不做赘述了,其核心就是迭代,没迭代一次相当于从源点向外走了一步,有一点像BFS。而这个过程略作改造就可以解决本问题。原型核心代码如下:

while (true)
{
    bool changed = 0;
    for (int i = 0; i < n; i++)
    {
        // j -> i
        for (int j = 0; j < n; j++)
        {
            if (graph[j][i] < inf && ans[i] > bak_ans[j] + graph[j][i])
            {
                ans[i] = bak_ans[j] + graph[j][i];
                changed = 1;
            }
        }
    }
    if (!changed)
        break;
}

为什么要改造呢?因为我们现在要求每一步迭代(即while中的部分)只能走一步。而假想一个图,1->2,2->3,1->3,求1->3的单源最短路径,第一次迭代中,ans[2]被更新(相当于从1到2),紧接着ans[3]借着刚刚更新的ans[2]被更新(相当于从2到3),即这一次迭代中走了两步。(如果1->3的距离大于1->2加2->3的距离,那么第一次迭代之后保留的就是后者。)如果是这样的话,我们就没法通过控制迭代次数来控制最多走多少边了。因此,我们不能让ans[3]更新时享用同一次迭代中ans[2]刚刚更新的数值,而只能让它用上一轮迭代后的数值,这样一次迭代就只能走一步了。

于是,只要做一个数据分离就可以解决一次迭代走多步的问题了。修改后(把while循环改成了对k的循环),很容易得到完整的代码如下,实现了最多走K+1条边,或说最多通过K个点转移的效果。

class Solution
{
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K)
    {
        // bellman-ford
        int graph[100][100] = { 0 };
        memset(graph, 0x3f, sizeof(graph));
        const int inf = 60000000;
        for (auto iter : flights)
        {
            graph[iter[0]][iter[1]] = iter[2];
        }
        int ans[100] = { 0 };
        memset(ans, 0x3f, sizeof(ans));
        ans[src] = 0;
        for (int k = 1; k <= K + 1; k++)
        {
            bool changed = 0;
            int bak_ans[100] = { 0 };
            for (int i = 0; i < n; i++)
                bak_ans[i] = ans[i];
            for (int i = 0; i < n; i++)
            {
                // j -> i
                for (int j = 0; j < n; j++)
                {
                    if (graph[j][i] < inf && ans[i] > bak_ans[j] + graph[j][i])
                    {
                        ans[i] = bak_ans[j] + graph[j][i];
                        changed = 1;
                    }
                }
            }
            if (!changed)
                break;
        }
        int res = ans[dst] < inf ? ans[dst] : -1;
        return res;
    }
};
Last modification:June 24th, 2020 at 03:52 pm
如果觉得我的文章对你有用,请随意赞赏