Dijkstra（迪杰斯特拉）算法

采用广度优先搜索思想，对有向赋权图寻找最短路径。
该算法对于不含负权的有向图来说，是目前已知的最快的单源最短路径算法。
时间复杂度：O（n^2）
基本原理：不断为为每个顶点 v 保留目前为止所找到的从s到v的最短路径

上图为戴克斯特拉算法应用示意图。
起点以左下角的红点，目标是右上角的绿点，中间灰色的倒L型为障碍物。蓝色空圈表示”暂定”，用以搜索下一步；已经填充颜色的表示探访过，图中颜色以红到绿，越绿表示离起点越远。所有节点都被均匀的探索。

我们以下图为例：

假设以“1”为顶点出发，求解到每个顶点的最短路径，若可达，则输出最短路径；若不可达，则输出无穷大（32767）

shortest(1, 2)=2

shortest(1, 3)=4

shortest(1, 4)=5
注：经对比，第二种路径得到的权值和较小，取第二种方式


shortest(1, 5)=2

算法如下：

void dijkstra(AdjMatrix *G)
{
    int i,j;
    int min,minid;
    int tmp;
    int vs;
    int prev[MAX] = {0};
    int dist[MAX] = {0};
    int visited[MAX];      // visited[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。

    // 初始化
    printf("请输入要查询的单源顶点");
    scanf("%d",&vs);
    vs-=1;
    for (i = 0; i < G->numV; i++)
    {
        visited[i] = 0;              // 顶点i的最短路径还没获取到。
        prev[i] = 0;              // 顶点i的前驱顶点为0。
        dist[i] = G->Edge[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
    }
    // 对"顶点vs"进行初始化
    visited[vs] = 1;//将顶点vs加入最短路径，对应的visited[i]置为1 
    dist[vs] = 0;//到自己的权为0 

    // 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
    for (i = 1; i < G->numV; i++)
    {
        // 寻找当前最小的路径；
        // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(minid)。
        min = INF;
        for (j = 0; j < G->numV; j++)
        {
            if (visited[j]==0 && dist[j]<min)
            {
                min = dist[j];
                minid = j;
            }
        }
        visited[minid] = 1;// 标记"顶点minid"为已经获取到最短路径

        // 更新当前最短路径和前驱顶点
        // 即，当已经"顶点minid的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
        for (j = 0; j < G->numV; j++)
        {
            tmp = (G->Edge[minid][j]==INF ? INF : (min + G->Edge[minid][j]));// 防止溢出 

            if (visited[j] == 0 && (tmp  < dist[j]) )
            {
                dist[j] = tmp;
                prev[j] = minid;
            }
        }
    }

    // 打印dijkstra最短路径的结果
    printf("dijkstra(%c): \n", G->Vertices[vs]);
    for (i = 0; i < G->numV; i++)
        printf("  shortest(%c, %c)=%d\n", G->Vertices[vs], G->Vertices[i], dist[i]);
}

具体代码如下：

#include<stdio.h>
#include<stdlib.h>
#define MaxVertices 100 //假设包含100个顶点
#define MaxWeight 32767 //不邻接时为32767，但输出时用 "∞"
#define MAX 100
#define INF         (~(0x1<<31)) 
typedef struct{ //包含权的邻接矩阵的的定义
    char Vertices[MaxVertices];  //顶点信息的数组
    int Edge[MaxVertices][MaxVertices]; //边的权信息的数组
    int numV; //当前的顶点数
    int numE; //当前的边数
}AdjMatrix;

void CreateGraph(AdjMatrix *G) //图的生成函数
{ 
    int n,e,vi,vj,w,i,j;
    printf("请输入图的顶点数和边数（以空格分隔）：");
    scanf("%d%d",&n,&e);
    G->numV=n;G->numE=e;
    for(i=0;i<n;i++) //图的初始化
        for(j=0;j<n;j++)
            { 
            if(i==j)
                G->Edge[i][j]=0;
            else 
                G->Edge[i][j]=32767;
            }
    for(i=0;i<n;i++)
        for(i=0;i<G->numV;i++) //将顶点存入数组中
        { 
        printf("请输入第%d个顶点的信息(整型):",i+1);  
      // G->adjlist[i].vertex=getchar(); 
        scanf(" %c",&G->Vertices[i]);
        }
    printf("\n");

    for(i=0;i<G->numE;i++)
    { 
        printf("请输入边的信息i,j,w(以空格分隔):");
        scanf("%d%d%d",&vi,&vj,&w); 
        //若为不带权值的图，则w输入1
        //若为带权值的图，则w输入对应权值

        G->Edge[vi-1][vj-1]=w;//①
        //G->Edge[vj-1][vi-1]=w;//②
        //无向图具有对称性的规律，通过①②实现
        //有向图不具备此性质，所以只需要①
    }
}
void DispGraph(AdjMatrix G) //输出邻接矩阵的信息
{ 
    int i,j;
    printf("\n输出顶点的信息（整型）:\n");
    for(i=0;i<G.numV;i++)
        printf("%8c",G.Vertices[i]);

    printf("\n输出邻接矩阵:\n");
    printf("\t");
    for(i=0;i<G.numV;i++)
        printf("%8c",G.Vertices[i]);

    for(i=0;i<G.numV;i++)
    { 
        printf("\n%8d",i+1);
        for(j=0;j<G.numV;j++)
        { 
        if(G.Edge[i][j]==32767) 
        //两点之间无连接时权值为默认的32767，但输出时为了方便输出 "∞"
            printf("%8s", "∞");
        else
            printf("%8d",G.Edge[i][j]);
        }
        printf("\n");   
    }
}
void dijkstra(AdjMatrix *G)
{
    int i,j;
    int min,minid;
    int tmp;
    int vs;
    int prev[MAX] = {0};
    int dist[MAX] = {0};
    int visited[MAX];      // visited[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。

    // 初始化
    printf("请输入要查询的单源顶点");
    scanf("%d",&vs);
    vs-=1;
    for (i = 0; i < G->numV; i++)
    {
        visited[i] = 0;              // 顶点i的最短路径还没获取到。
        prev[i] = 0;              // 顶点i的前驱顶点为0。
        dist[i] = G->Edge[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
    }
    // 对"顶点vs"进行初始化
    visited[vs] = 1;//将顶点vs加入最短路径，对应的visited[i]置为1 
    dist[vs] = 0;//到自己的权为0 

    // 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
    for (i = 1; i < G->numV; i++)
    {
        // 寻找当前最小的路径；
        // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(minid)。
        min = INF;
        for (j = 0; j < G->numV; j++)
        {
            if (visited[j]==0 && dist[j]<min)
            {
                min = dist[j];
                minid = j;
            }
        }
        visited[minid] = 1;// 标记"顶点minid"为已经获取到最短路径

        // 更新当前最短路径和前驱顶点
        // 即，当已经"顶点minid的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
        for (j = 0; j < G->numV; j++)
        {
            tmp = (G->Edge[minid][j]==INF ? INF : (min + G->Edge[minid][j]));// 防止溢出 

            if (visited[j] == 0 && (tmp  < dist[j]) )
            {
                dist[j] = tmp;
                prev[j] = minid;
            }
        }
    }

    // 打印dijkstra最短路径的结果
    printf("dijkstra(%c): \n", G->Vertices[vs]);
    for (i = 0; i < G->numV; i++)
        printf("  shortest(%c, %c)=%d\n", G->Vertices[vs], G->Vertices[i], dist[i]);
}
int main()
{ 
    AdjMatrix G;
    freopen("1.txt","r",stdin);
    CreateGraph(&G);
    dijkstra(&G);
    DispGraph(G);

}

注：该算法是在邻接矩阵的基础上完成的，请参照邻接矩阵（C语言）

注：由于测试输入数据较多，程序可以采用文件输入
5 7
1
2
3
4
5
1 2 2
1 3 4
1 5 2
2 3 1
2 4 6
3 4 2
4 5 3
2