Dijkstra算法应用举例.docVIP

Dijkstra算法应用举例 20061002516 张昕 123062 16 某城市部分街道如下图所示 求到其他点的最短距离。 源程序如下 #include stdio.h #include stdlib.h #define TRUE 1 #define FALSE 0 #define MAXV 100 #define MAXDEGREE 50 #define MAXINT 100007 int parent[MAXV]; typedef struct { int v; int weight; } edge; typedef struct { edge edges[MAXV+1][MAXDEGREE]; int degree[MAXV+1]; int nvertices; int nedges; } graph; initialize_graph(graph* g) { int i; g - nvertices = 0; g - nedges = 0; for (i=1; i=MAXV; i++) g-degree[i] = 0; } insert_edge(graph* g,int x,int y,int directed,int w) { if (g-degree[x] MAXDEGREE) printf(Warning: insertion(%d,%d) exceeds degree bound\n,x,y); g-edges[x][g-degree[x]].v = y; g-edges[x][g-degree[x]].weight = w; g-degree[x] ++; if (directed == FALSE) insert_edge(g,y,x,TRUE,w); else g-nedges ++; } read_graph(graph* g,int directed) { int i; int m; int x,y,w; initialize_graph(g); char* m_n = 8 12; //eg 3 1 4 ---v3节点与v1节点互连 权值是4 char* s[] = {1 2 2, 1 3 5, 1 4 3, 2 3 4, 2 5 6, 3 4 4, 3 6 5, 4 7 4, 5 6 3, 5 8 4, 6 7 5, 6 8 4, 7 8 6 }; sscanf(m_n,%d %d,(g-nvertices),m); for (i=1; i=m; i++) { sscanf(s[i-1],%d %d %d\n,x,y,w); insert_edge(g,x,y,directed,w); } } find_path(int start,int end,int parents[]) { if ((start == end) || (end == -1)) printf(\n%d,start); else { find_path(start,parents[end],parents); printf( %d,end); } } void dijkstra(graph *g, int start) { int i,j; bool intree[MAXV];