Dijkstra算法求最短路径

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <limits.h>
  5 
  6 #pragma warning(disable:4996)
  7 
  8 #define MAX_NAME 10
  9 #define MAX_VERTEX_NUM 26
 10 
 11 typedef char VertexType[MAX_NAME];
 12 typedef unsigned int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接距阵
 13 
 14 struct MGraph//定义网
 15 {
 16     VertexType vexs[MAX_VERTEX_NUM];
 17     AdjMatrix arcs;
 18     int vexnum, arcnum;
 19 };
 20 
 21 int LocateVex( MGraph& G, VertexType u ) //定位
 22 {
 23     register int i;
 24 
 25     for ( i = 0; i < G.vexnum; ++ i )
 26     {
 27         if ( strcmp( u, G.vexs[i] ) == 0 )
 28         {
 29             return i;
 30         }
 31     }
 32     return -1;
 33 }
 34 
 35 void CreateDN( MGraph& G ) //建网
 36 {
 37     int i, j, k, w;
 38     VertexType va, vb;
 39 
 40     printf( "请输入有向网G的顶点数和弧数(以空格作为间隔)
" );
 41     scanf( "%d %d", &G.vexnum, &G.arcnum );
 42 
 43     memset( G.vexs, 0, sizeof( G.vexs ) );
 44     printf( "请输入%d个顶点的值(<%d个字符):
", G.vexnum, MAX_NAME );
 45     for ( i = 0; i < G.vexnum; ++ i )
 46     {
 47         scanf( "%s", G.vexs[i] );
 48     }
 49 
 50     memset( G.arcs, 0xff, sizeof( G.arcs ) );
 51     printf( "请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): 
", G.arcnum );
 52     for ( k = 0; k < G.arcnum; ++ k )
 53     {
 54         scanf( "%s%s%d%*c", va, vb, &w );
 55         i = LocateVex( G, va );
 56         j = LocateVex( G, vb );
 57         G.arcs[i][j] = w;
 58     }
 59 }
 60 
 61 typedef unsigned int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 62 typedef unsigned int ShortPathTable[MAX_VERTEX_NUM];
 63 
 64 void ShortestPath_DIJ( MGraph& G, int v0, PathMatrix P, ShortPathTable D )
 65 {
 66     int v, w, i;
 67     unsigned int min;
 68     unsigned int final[MAX_VERTEX_NUM];
 69 
 70     for ( v = 0; v < G.vexnum; ++ v )
 71     {
 72         final[v] = 0;
 73         D[v] = G.arcs[v0][v];
 74 
 75         memset( P[v], 0, sizeof( int ) * G.vexnum );
 76 
 77         if ( D[v] < UINT_MAX )
 78         {
 79             P[v][v0] = P[v][v] = 1;
 80         }
 81     }
 82 
 83     D[v0] = 0;
 84     final[v0] = 1;
 85     for ( i = 1; i < G.vexnum; ++ i )
 86     {
 87         min = UINT_MAX;
 88         for ( w = 0; w < G.vexnum; ++ w )
 89         {
 90             if ( !final[w] && D[w] < min )
 91             {
 92                 v = w;
 93                 min = D[w];
 94             }
 95         }
 96 
 97         final[v] = 1;
 98 
 99         for ( w = 0; w < G.vexnum; ++ w )
100         {
101             if ( !final[w] && min < UINT_MAX && G.arcs[v][w] < UINT_MAX && ( min + G.arcs[v][w] < D[w] ) )
102             {
103                 D[w] = min + G.arcs[v][w];
104                 memcpy( P[w], P[v], sizeof( int ) * G.vexnum );
105                 P[w][w] = 1;
106             }
107         }
108     }
109 }
110 
111 int main()
112 {
113     int i, j;
114     MGraph g;
115     PathMatrix p;
116     ShortPathTable d;
117 
118     CreateDN( g );
119 
120     ShortestPath_DIJ( g, 0, p, d ); //以g中位置为0的顶点为源点，球其到其余各顶点的最短距离。存于d中
121 
122     printf( "最短路径数组p[i][j]如下:
" );
123     for ( i = 0; i < g.vexnum; ++ i )
124     {
125         for ( j = 0; j < g.vexnum; ++ j )
126         {
127             printf( "%2d", p[i][j] );
128         }
129         printf( "
" );
130     }
131 
132     printf( "%s到各顶点的最短路径长度为：
", g.vexs[0] );
133     for ( i = 1; i < g.vexnum; ++i )
134     {
135         if ( d[i] != UINT_MAX )
136         {
137             printf( "%s-%s:%d
", g.vexs[0], g.vexs[i], d[i] );
138         }
139         else
140         {
141             printf( "%s-%s:无路
", g.vexs[0], g.vexs[i] );
142         }
143     }
144 
145     system( "PAUSE" );
146     return 0;
147 }

/*
请输入有向网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
请按任意键继续. . .
*/