求最短路径，这个算法没有什么特别的，对于算法入门，这个算法要熟练的写出来。

刚刚写了一遍，现在再写一遍，把思路一遍写出。c语言形式。

首先是图的数据结构，处理这个算法的时候用的是图的邻接矩阵。

考虑一下定义，有图中顶点，构成的邻接矩阵，顶点数与边数。

typedef struct MGraph

{

char vexs[MAXVEX];

int arc[MAXVEX][MAXVEX];

int numVertexes,numEdges;

}MGraph;

我们先申明两个函数，一个创建图，一个计算最短距离。

void createMGraph(MGraph *g);

void shortPathDijkstra(MGraph g,int v0,int p[],int s[]);

创建图这个不多说。

void createMGraph(MGraph *g)

{

    int i,j;

    g->numEdges=16;

    g->numVertexes=9;

    for(i=0;i<MAXVEX;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]=INFINITY;

            }

        }

    }

    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];

        }

    }

}

好，求最短距离，从代码中看思路。先看整个代码

void shortPathDijkstra(MGraph g,int v0,int p[],int s[])

{

    int v,w,k,min;

    int final[MAXVEX];

    for(v=0;v<g.numVertexes;v++)

    {

        final[v]=0;

        s[v]=g.arc[v0][v];

        p[v]=0;

    }

    s[v0]=0;

    final[v0]=1;

    for(v=1;v<g.numVertexes;v++)

    {

        min = INFINITY;

        for(w=0;w<g.numVertexes;w++)

        {

            if(!final[w]&&s[w]<min)

            {

                k=w;

                min=s[w];

            }

        }

        final[k]=1;

        for(w=0;w<g.numVertexes;w++)

        {

            if(!final[w]&&(min+g.arc[k][w]<s[w]))

            {

                s[w] = min+g.arc[k][w];

                p[w] = k;

            }

        }

    }

}

第一块数据处理化，这个不用多说。下面就开始计算v0到每个点的最短距离，给出for循环计算每个点，从v1开始。

for(v=1;v<g.numVertexes;v++)

我们对最短距离进行依次更改，在一开始初始化的时候，我们对v0直接连接的点的距离加入到待确定最短距离当中。

之后我们对点v1进行处理时，将v1连接的点距离加上最短距离跟待确定最短距离进行比较，如果小于待确定最短距离，则更改该距离，待循环到该点之后变为确定最短距离。

依次循环。

最后给出完整代码：

#include 
    
     #define MAXVEX 9#define INFINITY 65535//定义一个图结构typedef struct MGraph{    char vexs[MAXVEX];    int arc[MAXVEX][MAXVEX];    int numVertexes,numEdges;}MGraph;void createMGraph(MGraph *g);void shortPathDijkstra(MGraph g,int v0,int p[],int s[]);void createMGraph(MGraph *g){    int i,j;    g->numEdges=16;    g->numVertexes=9;    for(i=0;i
     
      vexs[i]=i;    }    for(i=0;i
      
       numVertexes;i++)    {        for(j=0;j
       
        numVertexes;j++)        {            if(i==j)            {                g->arc[i][j]=0;            }            else            {                g->arc[i][j]=g->arc[j][i]=INFINITY;            }        }    }    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
        
         numVertexes;i++)    {        for(j=i;j
         
          numVertexes;j++) { g->arc[j][i] =g->arc[i][j]; } }}void shortPathDijkstra(MGraph g,int v0,int p[],int s[]){ int v,w,k,min; int final[MAXVEX]; for(v=0;v