数据结构与算法－求最短路径之迪杰斯特拉（Dijkstra）算法

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径，它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

1. 算法步骤；

1. 初始时，引进两个集合S和U，S只包含起点s，U包含除s外的其他顶点，且U中顶点的距离为起点s到该顶点的距离；

2. 从U中选出距离最短的顶点k，并将顶点k加入到S中，同时，将从U中移除顶点k；

3. 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离。

4. 重复步骤2和3，直到遍历完所有顶点。

2. 算法实例；

以图G4为例，以D为起点对该算法进行演示。

 以下是实现步骤

3. 算法实现；

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int inf = 1 << 29;

int main(){
    int map[10][10], t1, t2, t3, min, u, n, m;
    int dis[10];
    int vis[10];
    scanf("%d%d", &n, &m);
    // 初始化
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (i == j){
                map[i][j] = 0;
            }else{
                map[i][j] = inf;
            }
        }
    };
    // 读入边
    for (int i = 1; i <= m; i++){
        scanf("%d%d%d", &t1, &t2, &t3);
        map[t1][t2] = t3;
    };
    // 初始化dis数组，表示1号顶点到其余各个顶点的最短路程
    for (int i = 1; i <= n; i++){
        dis[i] = map[1][i];
    };
    // 初始化vis
    for (int i = 1; i <= n; i++){
        vis[i] = 0;
    };
    // 标记起始点1已经被访问过
    vis[1] = 1; 
    // 迪杰斯特拉算法(Dijkstra)的核心内容
    // 因为松弛的是边数，所以是n-1
    for (int i = 1; i <= n - 1; i++){
        min = inf;
        for (int j = 1; j <= n; j++){
            if (vis[j] == 0 && dis[j] < min){
                min = dis[j];
                u = j;
            }
        };
        vis[u] = 1;
        for (int v = 1; v <= n; v++){
            if (map[u][v] < inf){
                if (dis[u] + map[u][v] < dis[v]){
                    dis[v] = dis[u] + map[u][v];
                }
            }
        }
    };
    for (int i = 1; i <= n; i++){
        printf("%d ", dis[i]);
    }
    return 0;
}

由以上代码中的循环可知，迪杰斯特拉(Dijkstra)算法的时间复杂度是O（n^2）