《Dijkstra算法应用举例.pdf》由会员分享，可在线阅读，更多相关《Dijkstra算法应用举例.pdf（9页珍藏版）》请在三一文库上搜索。
1、Dijkstra 算法应用举例 20061002516 张昕123062 16 某城市部分街道如下图所示 求 1 v到其他点的最短距离。 源程序如下 #include #include #define TRUE 1 #define FALSE 0 #define MAXV 100 #define MAXDEGREE 50 #define MAXINT 100007 int parentMAXV; typedef struct int v; int weight; edge; typedef struct edge edgesMAXV+1MAXDEGREE; int degreeMAXV+1;
2、3 v 4 v 6 v 7 v 2 4 5 3 4 6 5 3 5 4 6 4 1 v 2 v 5 v 8 v 4 int nvertices; int nedges; graph; initialize_graph(graph* g) int i; g - nvertices = 0; g - nedges = 0; for (i=1; idegreei = 0; insert_edge(graph* g,int x,int y,int directed,int w) if (g-degreex MAXDEGREE) printf(“Warning: insertion(%d,%d) exc
3、eeds degree boundn“,x,y); g-edgesxg-degreex.v = y; g-edgesxg-degreex.weight = w; g-degreex +; 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 =
4、 “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“, for (i=1; invertices; i+) intreei = FALSE; distancei = MAXINT; parenti = -1; distancestart = 0; v = start; while (intreev = FALSE) intreev = TRUE; for (i=0; ideg
5、reev; i+) w = g-edgesvi.v; weight = g-edgesvi.weight; if (distancew (distancev+weight) distancew = distancev+weight; parentw = v; v = 1; dist = MAXINT; for (i=1; invertices; i+) if (intreei = FALSE) v = i; for (i=1; invertices; i+) printf(“%d %dn“,i,distancei); int main(int argc,char* argv) graph g;
6、 int i,j; read_graph( for(j=1;j=8;j+) printf(“n“); printf(“ 输出到各点的最短路径长度n“); dijkstra( printf(“ 输出到各点的最短路径n“); for (i=1; i=g.nvertices; i+) find_path(j,i,parent); printf(“n“); system(“PAUSE“); return 0; 运行结果 1 到各点的最短路经及长度 2 到各点的最短路经及长度 3 到各点的最短路经及长度 4 到各点的最短路经及长度 5 到各点的最短路经及长度 6 到各点的最短路经及长度 7 到各点的最短路经及长度 8 到各点的最短路经及长度 若修改 char* m_n = “8 12“; 8表示 8 个节点。 /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“ ; 则可推广到大量节点的复杂图中的点之间最短路径的求解。