最短路径（Dijkstra）

#include<iostream> using namespace std; typedef char VertexType; typedef int EdgeType; const int MAXVEX = 100; const int INFINITY = 65535; typedef int Patharc[MAXVEX]; typedef int shortPathTable[MAXVEX]; typedef struct { VertexType vexs[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numVertexes,numEdges; }MGraph; //D记录V0点到其他顶点的路劲总权值，P记录所经过哪些点 void ShortestPath_Dijkastra(MGraph *G,Patharc *P,shortPathTable *D) { int i , j, k, min; int final[MAXVEX]; for(i = 0;i < G->numVertexes;++i) { (*D)[i] = G->arc[0][i]; (*P)[i] = 0; final[i] = 0; } final[0] = 1; for(i = 0;i < G->numVertexes;++i) { min = INFINITY; for(j = 0;j < G->numEdges;++j) { if(!final[j] && (*D)[j] < min) { k = j; min = (*D)[j]; } } final[k] = 1; for(j = 0;j < G->numEdges;++j) { if(!final[j] && (min + G->arc[k][j]) < (*D)[j]) { (*D)[j] = min + G->arc[k][j]; (*P)[j] = k; } } } } /* 建立无向网图的邻接矩阵表示 */ void CreateMGraph_Undirected(MGraph *G) { int i,j,k,w; cin>>G->numVertexes>>G->numEdges; for(i = 0;i < G->numVertexes;++i)//输入顶点 { cin>>G->vexs[i]; } for(i = 0;i < G->numVertexes;++i)//初始化邻接矩阵,除对角线元素 = 0，其余为INFINITY; { for(j = 0;j < G->numVertexes;++j) { if(i == j) { G->arc[i][j] = 0; } else { G->arc[i][j] = INFINITY; } } } for(k = 0;k < G->numEdges;++k)//完成邻接矩阵的填写工作 { cin>>i>>j>>w; G->arc[i][j] = G->arc[j][i] = w; } } void ShowMGraph(MGraph *G)//打印图的信息 { cout<<"图的顶点，边数为："<<G->numVertexes<<","<<G->numEdges<<endl; cout<<"邻接矩阵为："<<endl; for(int i = 0;i < G->numVertexes;++i) { for(int j = 0;j < G->numVertexes;++j) { if(G->arc[i][j] == INFINITY) { cout<<"# "; } else { cout<<" "<<G->arc[i][j]<<" "; } } cout<<endl; } } int main() { MGraph *G = new MGraph(); Patharc P; shortPathTable D; CreateMGraph_Undirected(G); ShowMGraph(G); ShortestPath_Dijkastra(G,&P,&D); delete G; }