代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define MAXN (10001)
#define INF (1<<16)
typedef struct _Vertex
{
int w[MAXN];
int cw;
int know;
int dis;
int path;
int ew[MAXN]; /*The edge weight of curent vertex to w[i] */
}Graph;
Graph G[MAXN];
int read_graph ( void )
{
int i, k;
int n, m, ew;
scanf ("%d", &n );
for ( i = 0 ; i < n; i ) {
scanf ("%d", &m ); G[i].cw = m; G[i].know = 0; G[i].dis = INF; G[i].path = -1;
for ( k = 0; k < m; k ) scanf ("%d%d", &G[i].w[k], &G[i].ew[k] );
}
return n;
}
int find ( int n )
{
int i;
int m;
for ( m = -1, i = 0; i < n; i ) if ( !G[i].know ) { m = i; break; }
if ( m < 0 ) return -1;
for ( i = m 1; i < n; i ) {
if ( !G[i].know ) {
if ( G[i].dis < G[m].dis ) m = i;
}
}
return m;
}
void dijst ( int v , int n)
{
int i, k;
int min;
int *w = NULL;
int cw;
G[v].dis = 0;
while (1) {
min = find ( n );
if ( min < 0 ) { /*Have no vertex to continue*/
break;
}
G[min].know = 1;
w = G[min].w; cw = G[min].cw;
for ( i = 0; i < cw; i ) {
if ( !G[ w[i] ].know ) {
if ( G[min].dis G[min].ew[i] < G[ w[i] ].dis ) {
G[ w[i] ].dis = G[min].dis G[min].ew[i];
G[ w[i] ].path = min;
}
}
}
}
}
void print_path ( int v )
{
if ( G[v].dis > 0 ) {
print_path ( G[v].path );
printf ("->v%d", v 1 );
} else
printf ("v%d", v 1 );
}
int main(int argc, char *argv[])
{
int n;
int i;
freopen ( "data.txt" , "r" , stdin );
n = read_graph ();
dijst ( 0 , n );
for ( i = 0; i < n; i ) {
print_path ( i );
printf("n");
}
return 0;
}输入数据：
7 2 1 2 3 1 2 3 3 4 10 2 5 5 0 4 4 2 2 4 2 5 8 6 4 1 6 6 0 1 5 1
参考书籍：数据结构与算法分析（C语言描述第二版）
