Dijkstra算法(最短路).doc

/*Dijkstra(最短路)算法*/#include /预编译命令#include /定义了INT_MAXusing namespace std;unst int SIZE; /图中顶点总数/Function name :Dijkstra/Description :计算有向图中起点到终点的最短距离/Return type :int,最短路的长度/Argument :int EdgeSIZESIZE,输入参数，图信息/Argument :int nStart,输入参数，起点/Argument :int Dest,输入参数，终点/Argument :int PathSIZE,返回参数，路径信息int Dijkstra(int EdgeSIZESIZE, int nStart, int Dest, int PathSIZE)int MinDisSIZE; /起点到个点最短路径长度bool InS2SIZE; /标志各点是否在 S2中/初始化int i;for(i=0;iSIZE;i+) InS2i=true;InS2nStart=false; /初始状态只有nStart在S1中，其余在S2中for(i=0;iSIZE;i+) MinDisi=EdgenStarti; /初始各点的最大距离 if (EdgenStarti INT_MAX) Pathi=nStart; /最短路径的前一点 else Pathi=-1; /表示前一点不存在/进行计算while(InS2nDest) /当nDest还在S2内则计算 /查找S2中最短路径长度最小值的点 int nMinLen=INT_MAX; /最短路径长度的最小值 int nPoint=-1; /拥有最小值的点 for(i=0;iSIZE;i+) /查找 if(InS2i) & (MinDisinMinLen) nMinLen=MinDisi; nPoint=i; If(nMinLen=INT_MAX) /S2中的点不能从起点走到 break; /更新S2和MinDis InS2nPoint=false; /该点从S2移入S1 for(i=0;iSIZE;i+) if(InS2i) & (EdgenPointiINT_MAX) /对于在S2中的带您与该点有边相连 int nNewLen=nMinLen+EdgenPointi; if(nNewLenMinDisi) /如果原路径长 Pathi=nPoint; /更新路径 MinDisi=nNewLen; /更新路径长度 Return MinDisnDest;/Function name :OutputPath/Description :输出路径信息/Return type :void/Argument :int PathSIZE,路径信息/Argument :int nDest,终点void OutputPath(int PathSIZE,int nDest) if(PathnDest=-1) cout”没有从起点到v”nDest”的路径”endl; else if(PathnDest=nDest) /是起点 coutvnDest; else OutputPath(Path,PathnDest); /输出前面的路径 coutv”nDest; /输出这一段边int main() /主函数 int EdgeSIZESIZE; int i,j; /图信息/构造图信息 for(i=0;iSIZE;i+) for(j=0;jSIZE;j+) Edgeij=INT_MAX; Edgeij=0; Edge01=10; Edge02=12; Edge13=10; Edge24=7; Edge30=15; Edge31=12; Edge34=7; int PathSIZE; /记录最短路径信息 int nPathLength=Dijkstra(Edge,0,4,Path) /计算v0到v4的最短路径长度 if(nPathLength=INT_MAX) cout”从v0到v4没有路径可通”endl; else cout” 从v0到v4的路径为：”endl; OutputPath(Path,4); /输出