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

首先,读读这个

单源最短路径问题是”找到一个有向图中从一点到另外一点的最短路径”
单源最短路径问题与上述问题非常相似。首先考察较为简单的无权最短路径问题

无权最短路径

我们考察下边的图(图中每一条边的开销都是相同的):
dijk1
试图找出从节点1到节点3的最短路径,我们该如何完成?

解决这个问题的步骤大致如下:

  1. 对每个节点建立距离起点的距离的整形数据域,初始化为一个特殊值(表示尚未被记录),将起点标记为0
  2. 从起点开始,找到起点指向的所有没有记录过距离的节点集合M,在例子中是[2, 4],并将其距离记为起点距离+1,即1
  3. 将上述过程中产生的集合M的每一个节点作为新的起点重复过程2,如节点1之后的下一次操作就是:

    1. 对于节点4,它的M[5],将5的距离记为新的起点+1即2
    2. 对于节点2,它的’M’是[3],将3的距离记为新的起点+1即2
  4. 一旦所求终点的距离得到记录,即可以返回答案。如果目前的M集合再也不能进入新的节点(即所有可能标记的节点均被标记),而终点节点没有被标记,则表示终点不可达。

为什么要求M集合是没有记录过距离的节点?因为这个算法的遍历是同步的,对于一个已经被记录过距离的节点,它在你第二次遍历到它的时候一定拥有一个比目前更小的距离值。

这个算法也是广度优先算法的典型。

读读这个:这个文章的做法就是物理中的广度优先算法:物质基于化学势梯度,几乎等速度地均匀扩散,谁先扩散到终点,说明谁的路径更短。

编码实现

想要广度优先遍历,就一定要想到队列数据结构

假设我们的图是由邻接列表描述的:
经典的广度优先算法就用广度优先的典型写法(队列)来写:

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];
}

如果想要知道具体的路径,可以对于每一个节点增添一个数据域来维护最短路径中它的上一个节点。

测试:运行

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

得到结果2.


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