算法笔记 - Dijkstra算法

 

Dijkstra算法,译为迪杰斯特拉算法,使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题。Dijkstra算法不采用最小优先级队列的时间复杂度是 O(|V|^2)(其中|V|为图的顶点个数)。

算法思路

Dijkstra算法采用的是一种贪心的策略。

  1. 一个数组dp[]来保存源点s到各个顶点的最短距离
  2. 一个保存已经找到了最短路径的顶点的集合T(用数组T置1来表示该顶点已加入集合T,以下以~T表示未加入T的顶点集合)。

初始:

dp数组初始化为INF(无穷大),将源点s的dp值被赋为0(dp[s]=0),集合T为空(PS:第一次循环必定找到源点s加入T)。

循环:

  1. ~T中找到当前能到达的最近的顶点j(即dp数组中值最小的dp[j]),并且把该点j加入到T中,此时完成一个顶点;
  2. 我们需要看看新加入的顶点j是否可以到达~T中的其他顶点,并且看一下通过该顶点j到达其他点的路径长度是否比之前的最短路径还要短,如果是,那么就更新源点s到这些顶点的最短路径值(dp[]数组)。

然后,重复上述动作,直到T中包含了图的所有顶点。至此,dp[]中保存源点s到各个顶点的最短距离(dp[j]即源点s到j的最短路径)。

以下动图取自维基百科

Dijkstra算法

代码实现

若想获得源点s到所有可达顶点的最短路径,去掉参数e和相关判断。

/* 1. 初始化图的邻接矩阵,都是不可达;根据输入赋值,给邻接矩阵赋值 */
const int INF = __INT_MAX__;
fill(v[0], v[0] + n*n, INF);
...

/* 2. 调用 dijkstra 方法 */
void dijkstra(int s, int e, int n){     /* s:起点 e:终点 n:顶点个数 */
    int dp[n], T[n];
    /* 初始 */
    fill(dp, dp + n, INF);
    fill(T, T + n, 0);
    dp[s] = 0;
    /* 循环 */ 
    while (true) {
        int minp = INF, j = -1;
        /* 1. 查找不在T中且dp值最小的顶点,并将顶点j加入集合T */
        for(int i = 0; i < n; i++){
            if(T[i] == 0 && dp[i] < minp){
                j = i;
                minp = dp[i];
            }
        }
        if(j == -1) { 
            break; /* j == -1,则表示有些顶点从源点出发是不可达的,也可以退出循环 */
        }
        T[j] = 1;
        if(j == e) {    /* 查找到指定终点时,可以减少循环次数 */
            break;
        }
        /* 2. 利用新获得的dp[j]更新所有未在T集合中的顶点的dp值 */
        for(int i = 0; i < n; i++){ 
            if(T[i] == 0){  
                if(v[j][i] != INF) { /* j到i可达 */
                    if(dp[j] + v[j][i] < dp[i]){
                        dp[i] = dp[j] + v[j][i];
                        // 如果要记录路径,只需要在这将 path[i] 的路径更新为 path[j] + i;
                    }
                }
            }
        }
    }
}