本文共 1638 字，大约阅读时间需要 5 分钟。

Dijkstra算法

要求

求一个点（源点）到其余各个顶点的最短路径。

思路

先将源点到其余各个点的路径列出来dis[]，找到最小值，这个最小值就是源点到这一点u的最短路径，并标记已经找出，再以这个点开始，依次遍历到其它点v，如果这个点u到其它点v的距离加上源点到这个点距离（也就是刚刚找出的最短距离）还小于源点直接到点v的距离dis[v]，更新数组dis[v],再在dis[]找出最小值并标记，此时又求出一个点，重复步骤，n-1次后全部求出。

代码

#include 
   
    #define N 7#define M 7#define X 99999999int a[N][M] = {                { 0,  0,  0,  0,  0,  0,  0},                { 0,  0,  1, 12,  X,  X,  X},                     { 0,  X,  0,  9,  3,  X,  X},                     { 0,  X,  X,  0,  X,  5,  X},                     { 0,  X,  X,  4,  0, 13, 15},                { 0,  X,  X,  X,  X,  0,  4},                    { 0,  X,  X,  X,  X,  X,  0}                       };int dis[M] = {
  0};int book[M] = {
  0};void print_a() {    for (int i = 0; i < N; ++i)    {        for (int j = 0; j < M; ++j)        {            printf("%8d ", a[i][j]);        }        printf("\n");    }    printf("\n");}void printf_array(int *p) {    for (int i = 0; i < M; ++i)    {        printf("%8d ", p[i]);    }    printf("\n");}int main() {    int min;    int u;    for (int i = 1; i < M; ++i) {        dis[i] = a[1][i];    }    book[1] = 1;    printf_array(dis);    for (int i = 1; i < M-1; ++i) {        min = X;        for (int i = 1; i < M; ++i) {            if (book[i] == 0 && dis[i] < min) {                min = dis[i];                u = i;            }        }        book[u] = 1;     // 标记找到最短距离的点        for (int v = 1; v < M; ++v) {            if (a[u][v] < X) {                if (a[u][v] + dis[u] < dis[v]) {                    dis[v] = a[u][v] + dis[u];                }            }        }        printf_array(dis);    }    return 0;}
   

时间复杂度

O(N^2)