Archive:

#include <stdio.h> 2 #include <stdlib.h> 3 #define maxv 10 5 #include "graph.h" 6 void main() 7 {8 elem v0; 9 int v; 10 mgraph g; 11 printf("1. Initialize function test :\n"); 12 initial(g); 13 printf("2. Create function test :\n"); 14 create(g); Printf ("3. Output function test :\n"); 16 printg(g); Printf ("4. Find shortest path :\n"); Printf (" Please print source vertex data v0:"); 19 scanf("%c",&v0); 20 v=locate(g,v0); 21 dijkstra(g,v); 22 printf("5. Output shortest path :\n"); 23 printpath(g,v); 24 printf("\n"); 25}Copy the code
2 #define INF 32767 3 typedef struct MGraph 4 {5 elem VEXes [maxv]; Int edges[maxv][maxv]; Int n,e; // vertices n and edges e 8}mgraph; 9 void initial(mgraph &g) {11 int I,j; 12 g.e=0; 13 g.n=0; 14 for(j=0; j<maxv; [j]=0; 16 for(i=0; i<maxv; i++) 17 { 18 for(j=0; j<maxv; j++) 19 { 20 g.edges[i][j]=inf; 21} 22} 23} 24 int locate(mgraph g,elem u) 25 {26 for(int I =0; i<g.n; i++) 27 { 28 if(g.vexes[i]==u) 29 return i; 30 } 31 return -1; 32} 33 void create(mgraph &g) {35 int I,j,k,w; 36 elem u,v; 37 printf(" Please enter the number of vertices of the digraph :"); 38 scanf("%d",&g.n); 39 printf(" Please enter the arc number of the digraph :"); 40 scanf("%d",&g.e); 41 fflush(stdin); 42 printf(" Please enter character vertex data, such as ABCD:"); 43 for(j=0; j<g.n; j++) 44 scanf("%c",&g.vexes[j]); // Build the vertex table 45 fflush(stdin); 46 printf(" Please input information about arc, format: arc tail, arc head, weight \n"); 47 for(k=0; k<g.e; k++) 48 { 49 scanf("%c,%c,%d",&u,&v,&w); 50 i=locate(g,u); 51 j=locate(g,v); 52 g.edges[i][j]=w; 53 fflush(stdin); 58 {58 int I,j; 58} 55} 56 void printg(mgraph g) 59 printf(" Input graph's adjacency matrix stores information :\n"); 60 printf(" vertex data :\n"); 61 for(i=0; i<g.n; i++) 62 printf("%d: %c\n",i,g.vexes[i]); 63 printf(" adjacency matrix data :\n"); 64 for(i=0; i<g.n; i++) 65 { 66 for(j=0; j<g.n; J++) 67 {68 if (g.e dges [I] [j] = = inf) 69 printf (" up "); 70 else 71 printf("%3d",g.edges[i][j]); 72 } 73 printf("\n"); 74 } 75 } 76 int dist[maxv]; Int path[maxv]; int path[maxv]; Bool s[maxv]; 79 void dijkstra(mgraph g,int v) 80 {81 int mindis, I,j,u; 82 for(i=0; i<g.n; i++) 83 { 84 dist[i]=g.edges[v][i]; // The current shortest path length is initialized 85s [I]=false; If (g.dges [v][I]< INF)// initialize the last intermediate vertex of the currently found shortest path 87 path[I]=v; 88 else 89 path[i]=-1; 90 } 91 s[v]=true; Path [v]=0; For (I =0; i<g.n; I++)// loop until all vertices have shortest paths or no shortest paths 94 {95 mindis=inf; 96 u=-1; For (j=0; j<g.n; If ((dist[j] ==false)&&(dist[j]<mindis)) 100 {101 u=j; 102 mindis=dist[j]; 103} 104} 105 if(mindis<inf)// if(mindis<inf) 106 {107 s[u]=true; For (j=0; j<g.n; If (s[j]==false) 111 {112 if(g.dges [u][j]< INF && Dist [u]+ g.dges [u][j]<dist[j]) 113 {114 dist[j]=dist[u]+g.edges[u][j]; Path [j]=u; 116} 117} 118} 119} 120} 121} 122 void printPath (mgraph g,int v i,j,w; 125 int road[maxv]; Printf ("%c found shortest paths to other vertices :\n",g.v. 127 for(i=0; i<g.n; I ++) 128 {129 if(s[I]) 130 printf("%d: ", I); 131 else 132 printf("%d: none ", I); 133 } 134 printf("\n"); 135 for(i=0; i<maxv; i++) 136 road[i]=-1; 137 for(i=0; i<g.n; i++) 138 { 139 if((s[i]==true)&&(i! Printf (" the length of the shortest path from %c to %c is :%d\t path is :",g.v [v],g.v [I],dist[I]); 142 printf("%c->",g.vexes[v]); 143 w=path[i]; // the shortest path vertex 144 j=0; While (w! [j]=w; 148 j++; 149 w=path[w]; 150 } 151 for(j--; j>=0; J -) / / output the shortest path 152 {153 printf (" % c - > ", g.v exes [road [j]]). 154 road[j]=-1; 155 } 156 printf("%c\n",g.vexes[i]); Printf (" there is no path from %c to %c \n",g.v x [v],g.v x [I]); 161 160}}Copy the code

The running results are as follows: