/* * 2014-5-22 * 摘自http://blog.csdn.net/jnu_simba/article/details/8871794 * */ #include<iostream> using namespace std; #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; } MGraph; typedef int PathArc[MAXVEX]; typedef int ShortPathTable[MAXVEX]; /* 构建图 */ void CreateMGraph(MGraph *G) { int i, j; /* printf("请输入边数和顶点数:"); */ G->numEdges = 16; G->numVertexes = 9; for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ G->vexs[i] = i; for (i = 0; i < G->numVertexes; i++){/* 初始化图 */ for ( j = 0; j < G->numVertexes; j++){ if (i == j) G->arc[i][j] = 0; else G->arc[i][j] = G->arc[j][i] = INFINITY; } } G->arc[0][1] = 1; G->arc[0][2] = 5; G->arc[1][2] = 3; G->arc[1][3] = 7; G->arc[1][4] = 5; G->arc[2][4] = 1; G->arc[2][5] = 7; G->arc[3][4] = 2; G->arc[3][6] = 3; G->arc[4][5] = 3; G->arc[4][6] = 6; G->arc[4][7] = 9; G->arc[5][7] = 5; G->arc[6][7] = 2; G->arc[6][8] = 7; G->arc[7][8] = 4; for(i = 0; i < G->numVertexes; i++) for(j = i; j < G->numVertexes; j++) G->arc[j][i] = G->arc[i][j]; } /* Dijkstra算法,求有向网G的pos顶点到其余顶点v的最短路径P[v]及带权长度D[v] */ /* P[v]的值为前驱顶点下标,D[v]表示pos到v的最短路径长度和 */ /* pos 取值 0~MG.numVertexs-1 */ void ShortestPath_Dijkstra(MGraph MG, int pos, PathArc P, ShortPathTable D){ int v, w, k, min; int final[MAXVEX];/* final[w]=1表示求得顶点pos至w的最短路径 */ /*初始化*/ for (v = 0; v < MG.numVertexes; v++){ final[v] = 0;/* 全部顶点初始化为未知最短路径状态 */ D[v] = MG.arc[pos][v];/* 将与pos点有连线的顶点加上权值 */ P[v] = 0;/* 初始化路径数组P为0 */ } D[pos] = 0; /*说明源点pos自身的长度为0 */ P[pos] = -1; /* -1表示自身无前驱顶点*/ final[pos] = 1;/* pos至pos不需要求路径 */ /* 开始主循环,每次求得pos到某个v顶点的最短路径 */ for (v = 1; v < MG.numVertexes; v++){ min = INFINITY;/* 当前所知离pos顶点的最近距离 */ for (w = 0; w < MG.numVertexes; w++){ /* 寻找剩余未确认路径的节点中,离pos最近的顶点 */ if (final[w]==0 && D[w] < min){ k = w; min = D[w]; /* w顶点离pos顶点更近 */ } } final[k] = 1;/* 将目前找到的最近的顶点置为1 */ for (w = 0; w < MG.numVertexes; w++){/* 修正当前最短路径及距离 若D(pos->k->w)<D(w),则更新*/ if (!final[w] && (min + MG.arc[k][w] < D[w])){ /* 说明找到了更短的路径,修改D[w]和P[w] */ D[w] = min + MG.arc[k][w];/* 修改当前路径长度 */ P[w] = k; } } } /* 结束循环,若P[w] = pos;说明顶点w的前驱为pos */ } int main(void) { MGraph MG; PathArc P; ShortPathTable D; int i, j, pos = 0; CreateMGraph(&MG); ShortestPath_Dijkstra(MG, pos, P, D); cout << "逆序最短路径如下:" << endl; for (i = 8; i >= 0; i--) { j = i; while (P[j] != -1 && P[j] != 0) { cout << "v" << j << "<-" << "v" << P[j] << " "; j = P[j]; } cout << "v" << j << "<-" << "v" << pos << " "; cout << endl; } cout << endl; return 0; } /* 逆序最短路径如下: v8->v7 v7->v6 v6->v3 v3->v4 v4->v2 v2->v1 v1->v0 v7->v6 v6->v3 v3->v4 v4->v2 v2->v1 v1->v0 v6->v3 v3->v4 v4->v2 v2->v1 v1->v0 v5->v4 v4->v2 v2->v1 v1->v0 v4->v2 v2->v1 v1->v0 v3->v4 v4->v2 v2->v1 v1->v0 v2->v1 v1->v0 v1->v0 v0->v0 */