Dijkstra算法

Dijkstra算法适用于单源最短路径问题（即求源结点到所有其他顶点的最短路径），使用时需满足两个条件：

(1)边权没有负值

(2)稠密图

存储结构采用邻接矩阵，n为顶点数，m为边数

int graph[n][n];

memset(graph, 0x3f, sizeof(graph));
for (int i = 0; i < n; i++) graph[i][i] = 0;

若源结点为顶点s，dis[i]标示源结点s到顶点i的最短距离（初始化dis[s]为0，其他为0x3f3f3f3f），vis[i]标示顶点i是否已被访问（0是未访问，1是已访问，初始化为全0）

int dis[n], vis[n];

Dijkstra算法基于贪心，流程如下：

(1)遍历所有未被访问的顶点j（vis[j]为0），找到其中距离源结点s最短的顶点t（dis[t]为最短）

(2)标记t为已访问（vis[t]标记为1），用顶点t更新所有顶点j的dis[j]（如果dis[t] + graph[t][j] < dis[j]，则用dis[t] + graph[t][j]更新dis[j]）

(3)循环1、2步n-1次（每次标记一个顶点已访问，除源结点一共n-1个结点需要标记，所以循环n-1次）

for (int i = 1; i < n; i++) {
    int t = -1;
    for (int j = 0; j < n; j++)
        if (!vis[j] && (t == -1 || dis[j] < dis[t])) t = j;

    vis[t] = 1;
    for (int j = 0; j < n; j++)
        dis[j] = min(dis[j], dis[t] + graph[t][j]);
}

算法结束时，dis[i]存储源结点s到顶点i的最短距离，0x3f3f3f3f表明不可达

注解：

(1)Dijkstra算法第2步，本应是用顶点t更新其可达、未访问顶点j的dis[j]，可实现时更新操作却循环了所有顶点，这是由于没有负权边，不可达、已访问顶点j的dis[j]不会被更新，即使循环到也无妨

(2)Dijkstra算法适用于稠密图（稠密图定义参照图的存储结构）

---