最短路径定义

对于非网图，所谓最短路径是指两顶点之间经过的边数最少的路径；
对于网图，是指两顶点之间经过的边上权值和最少的路径。并且，我们称路径上的第一个顶点为源点，最后一个顶点为终点。

迪杰斯特拉(Dijkstra)算法

算法思路

1. 定义两个数组，P用来保存前驱顶点的下标，D用来保存从V0到当前顶点的最短路径长度和。
2. 先找到与指定顶点V0距离最短的顶点k。
3. 然后遍历与k顶点有关的所有路径，找到那些顶点与V0的较短路径。
4. 循环2-3步，最终得到从某个源点到其余各顶点的最短路径。

代码实现

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;
typedef struct{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/*用于存储最短路径下标的数组*/
typedef int Patharc[MAXVEX];
/*用于存储到各点最短路径权值的和*/
typedef int ShortPathTable[MAXVEX];

/*10.1 创建邻近矩阵*/
void CreateMGraph(MGraph *G){
    int i, j;
    
    G->numEdges=16;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)
    {
        G->vexs[i]=i;
    }
    
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=1;
    G->arc[0][2]=5;
    G->arc[1][2]=3;
    G->arc[1][3]=7;
    G->arc[1][4]=5;
    
    G->arc[2][4]=1;
    G->arc[2][5]=7;
    G->arc[3][4]=2;
    G->arc[3][6]=3;
    G->arc[4][5]=3;
    
    G->arc[4][6]=6;
    G->arc[4][7]=9;
    G->arc[5][7]=5;
    G->arc[6][7]=2;
    G->arc[6][8]=7;
    
    G->arc[7][8]=4;
    
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

/*10.2 求得网图中2点间最短路径
 Dijkstra 算法
 G: 网图;
 v0: V0开始的顶点;
 p[v]: 前驱顶点下标;
 D[v]: 表示从V0到V的最短路径长度和;
 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D){
    /*final[w] = 1 表示求得顶点V0~Vw的最短路径*/
    int final[MAXVEX] = {0};
    
    /*1.初始化数据*/
    for(int v = 0; v<G.numVertexes; v++){
        final[v] = 0;
        //因为从V0出发查找，先找到跟V0有关系的各顶点的路径
        (*D)[v] = G.arc[v0][v];
        (*P)[v] = 0;
    }
    (*P)[v0] = -1;//v0到V0是没有路径的
    (*D)[v0] = 0;//V0到V0的路径为0
    final[v0] = 1;//V0到V0是没有路径的.
    
    for(int v = 1; v<G.numVertexes; v++){
        int min = INFINITYC;
        int k =0;
        /*3.寻找离V0最近的顶点*/
        for(int w = 0; w<G.numVertexes; w++){
            //找到与V0距离最短的顶点，表示V0与该顶点是最短距离。
            if(final[w] != 1 && min > (*D)[w]){
                min = (*D)[w];
                k = w;
            }
        }
        //已经找到离V0最近的顶点，需要将该顶点的路径标志置为1，下次将不再查找该点
        final[k] = 1;
        
        /*4.把刚刚找到v0到k最短路径的基础上,对于k与 其他顶点的边进行计算,得到v0与它们的当前最短距离;*/
        for(int w = 0; w<G.numVertexes; w++){
            if(final[w] != 1 && (min+G.arc[k][w])<(*D)[w]){
                (*D)[w] = min+G.arc[k][w];
                (*P)[w] = k;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    printf("最短路径-Dijkstra算法\n");
    int i,j,v0;
    MGraph G;
    Patharc P;
    ShortPathTable D;
    v0=0;
    
    CreateMGraph(&G);
    
    ShortestPath_Dijkstra(G, v0, &P, &D);
    
    printf("最短路径路线:\n");
    for(i=1;i<G.numVertexes;++i)
    {
        printf("v%d -> v%d : ",v0,i);
        j=i;
        while(P[j]!=-1)
        {
            printf("%d ",P[j]);
            j=P[j];
        }
        printf("\n");
    }
    
    printf("\n最短路径权值和\n");
    for(i=1;i<G.numVertexes;++i)
        printf("v%d -> v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);
    
    printf("\n");
    return 0;
}

复法复杂度

Dijkstra算法因为有两层for循环，因此算法复杂度为O(n²)。