图论算法:Dijkstra算法 02 木灵的炼金工作室

我们在上一篇文章中实现了无权重图的单元最短路径算法,接下来我们考虑每一条边都有权重的情况。

赋权路径与无权路径最大的区别就是:无权路径算法中,一个节点一旦拥有了一个距离值,那么这个距离值一定是它的最小距离值,而赋权路径显然不是这样。在赋权路径中,后来的距离很有可能比先到的距离小。

如果按照无权路径的算法思想,我们可以有这两种思想:

  1. 以无权路径模拟,将每一条边的距离展开为若干节点。如A到B的距离为3,即可模拟A到B的路径是A->B1->B2->B,再用无权路径算法求解。
  2. 以无权路径的算法为基础,修改广度优先遍历时更新节点距离的方法为min()而不是++,同时取消"已经赋值的节点不能再被遍历"的限制。

想法1的漏洞是很明显的。权重的大小较小还好,如果有一条边的权重是’1E+20’呢?

那么我们就针对想法2来进行展开。

在此之前,我们首先需要假设你的图中没有负值圈。所谓负值圈,是循环一个周期时开销和为负值的圈。如果有这样的圈,那么所谓“最短路径算法”将不再是算法。

Dijkstra 算法

首先,我们必须允许节点距离的重复赋值,也就是说,我们上节的代码:

int unweightedPath (int totalNodeNumber, vector<vector <int>> Table, int start, int end) {
    vector<int> distance(totalNodeNumber, int(-1));
    queue<int> BFS;
    BFS.push(start);
    distance[start] = 0;
    
    int nowQueueSize;
    while (nowQueueSize = BFS.size()) {
        for (int i = 0; i < nowQueueSize; i++) {
            for (int j = 0; j < Table[BFS.front()].size(); j++) {
                if (distance[Table[BFS.front()][j]] != -1) continue;
                BFS.push(Table[BFS.front()][j]);
                distance[Table[BFS.front()][j]] = distance[BFS.front()] + 1;
            }
            BFS.pop();
        }
        if (distance[end] != -1) return distance[end];
    }
    return distance[end];
}

其中的if (distance[Table[BFS.front()][j]] != -1)必须被某种机制代替。
考虑:在什么情况下我们需要打破上述的限制呢?很直观地,在我求得的新距离值小于这一节点的原有距离值时,我们就需要对它更新,并且这一节点的新距离值可能会影响与它相连的其他节点的距离,因此,当上述情况发生,我们不仅需要更新节点的距离,我们还需要将它重新加入(一定是重新加入哦)我们的BFS队列中

这种算法就是Dijkstra算法的基本思想。实际的Dijkstra算法还有一条额外的条款:对于每一个节点,从它的最小权值边开始运行:因为从最小边开始运行的话,在算法的运行过程中,距离被修改的概率会更小,算法的运行效率会更高。

简单的代码实现如下:(pair<int, int>first是边的指向目标,second是边的权)

int Dijkstra (int totalNodeNumber, vector<vector<pair<int, int>>> Table, int start, int end) {
    vector<int> distance(totalNodeNumber, int(INT_MAX));
    queue<int> BFS;
    BFS.push(start);
    distance[start] = 0;
    
    int nowQueueSize;
    while (nowQueueSize = BFS.size()) {
        for (int i = 0; i < nowQueueSize; i++) {
            for (int j = 0; j < Table[BFS.front()].size(); j++) {
                if (distance[Table[BFS.front()][j].first] > distance[BFS.front()] + Table[BFS.front()][j].second){
                    BFS.push(Table[BFS.front()][j].first);
                    distance[Table[BFS.front()][j].first] = distance[BFS.front()] + Table[BFS.front()][j].second;
                }
                
            }
            BFS.pop();
        }
    }
    return distance[end];
}

所以为什么图中不可以存在负值圈呢?如果存在负值边,每绕一圈都会有至少一个节点被赋予新值,那么(nowQueueSize = BFS.size()) == 0的出循环条件将不会达成。

测试:运行

int main() {
    vector<vector<pair<int, int>>> test = {
        {}, 
        { {2, 10}, {4, 2} }, 
        { {3, 5} }, 
        {}, 
        { {5, 3} }, 
        { {2, 2}, {6, 1}, {7, 1} }, 
        { {3, 4} }, 
        { {8, 1} }, 
        { {6, 1} }
    };
    cout << Dijkstra(9, test, 1, 3);
    return 0;
}

输出结果10.


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn