Dijkstra算法求最短路径

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #include <limits.h>

 #pragma warning(disable:4996)

 #define MAX_NAME 10

 #define MAX_VERTEX_NUM 26

 typedef char VertexType[MAX_NAME];

 typedef unsigned int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接距阵

 struct MGraph//定义网

 {

     VertexType vexs[MAX_VERTEX_NUM];

     AdjMatrix arcs;

     int vexnum, arcnum;

 };

 int LocateVex( MGraph& G, VertexType u ) //定位

 {

     register int i;

     for ( i = ; i < G.vexnum; ++ i )

     {

         if ( strcmp( u, G.vexs[i] ) ==  )

         {

             return i;

         }

     }

     return -;

 }

 void CreateDN( MGraph& G ) //建网

 {

     int i, j, k, w;

     VertexType va, vb;

     printf( "请输入有向网G的顶点数和弧数(以空格作为间隔)\n" );

     scanf( "%d %d", &G.vexnum, &G.arcnum );

     memset( G.vexs, , sizeof( G.vexs ) );

     printf( "请输入%d个顶点的值(<%d个字符):\n", G.vexnum, MAX_NAME );

     for ( i = ; i < G.vexnum; ++ i )

     {

         scanf( "%s", G.vexs[i] );

     }

     memset( G.arcs, 0xff, sizeof( G.arcs ) );

     printf( "请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n", G.arcnum );

     for ( k = ; k < G.arcnum; ++ k )

     {

         scanf( "%s%s%d%*c", va, vb, &w );

         i = LocateVex( G, va );

         j = LocateVex( G, vb );

         G.arcs[i][j] = w;

     }

 }

 typedef unsigned int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

 typedef unsigned int ShortPathTable[MAX_VERTEX_NUM];

 void ShortestPath_DIJ( MGraph& G, int v0, PathMatrix P, ShortPathTable D )

 {

     int v, w, i;

     unsigned int min;

     unsigned int final[MAX_VERTEX_NUM];

     for ( v = ; v < G.vexnum; ++ v )

     {

         final[v] = ;

         D[v] = G.arcs[v0][v];

         memset( P[v], , sizeof( int ) * G.vexnum );

         if ( D[v] < UINT_MAX )

         {

             P[v][v0] = P[v][v] = ;

         }

     }

     D[v0] = ;

     final[v0] = ;

     for ( i = ; i < G.vexnum; ++ i )

     {

         min = UINT_MAX;

         for ( w = ; w < G.vexnum; ++ w )

         {

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

             {

                 v = w;

                 min = D[w];

             }

         }

         final[v] = ;

         for ( w = ; w < G.vexnum; ++ w )

         {

             if ( !final[w] && min < UINT_MAX && G.arcs[v][w] < UINT_MAX && ( min + G.arcs[v][w] < D[w] ) )

             {

                 D[w] = min + G.arcs[v][w];

                 memcpy( P[w], P[v], sizeof( int ) * G.vexnum );

                 P[w][w] = ;

             }

         }

     }

 }

 int main()

 {

     int i, j;

     MGraph g;

     PathMatrix p;

     ShortPathTable d;

     CreateDN( g );

     ShortestPath_DIJ( g, , p, d ); //以g中位置为0的顶点为源点，球其到其余各顶点的最短距离。存于d中

     printf( "最短路径数组p[i][j]如下:\n" );

     for ( i = ; i < g.vexnum; ++ i )

     {

         for ( j = ; j < g.vexnum; ++ j )

         {

             printf( "%2d", p[i][j] );

         }

         printf( "\n" );

     }

     printf( "%s到各顶点的最短路径长度为：\n", g.vexs[] );

     for ( i = ; i < g.vexnum; ++i )

     {

         if ( d[i] != UINT_MAX )

         {

             printf( "%s-%s:%d\n", g.vexs[], g.vexs[i], d[i] );

         }

         else

         {

             printf( "%s-%s:无路\n", g.vexs[], g.vexs[i] );

         }

     }

     system( "PAUSE" );

     return ;

 }

/*
请输入有向网G的顶点数和弧数(以空格作为间隔)
6 8
请输入6个顶点的值(<10个字符):
v1
v2
v3
v4
v5
v6
请输入8条弧的弧尾 弧头 权值(以空格作为间隔):
v1 v3 10
v1 v5 30
v1 v6 100
v2 v3 5
v3 v4 50
v4 v6 10
v5 v4 20
v5 v6 60
最短路径数组p[i][j]如下:
 0 0 0 0 0 0
 0 0 0 0 0 0
 1 0 1 0 0 0
 1 0 0 1 1 0
 1 0 0 0 1 0
 1 0 0 1 1 1
v1到各顶点的最短路径长度为：
v1-v2:无路
v1-v3:10
v1-v4:50
v1-v5:30
v1-v6:60
请按任意键继续. . .
*/