|
弗洛伊德算法 void ShortestPath_FLOYD（Mgraph G PathMatrix &p[] distancMatrix &D）{ //用Floyd不着算法注有向网G中各对顶点V和W之间的最短路径p[v][w]及其带权 //限长度d[v][w]若p[v][w][u]为TRUE则U是从V到W当前求得最短路径上的顶点 for（v=;v<Gvexnum;++v） for（w=;w<Gvexnum;++W）{ D[v][w]=Garcs[v][w]; for（u=;u<Gvexnum;++u） p[v][w][u]=FALSE; if（d[v][w]<INFINITY）{ P[v][w][v]=TRUE; P[v][w][w]=TRUE; }//if }//for for（u=;u<Gvexnum;++u） for（v=;v<Gvexnum;++v） for（w=;w<Gvexnum;++w） if{D[w][u]+D[u][w]<D[v][w]} {D[v][w]=D[v][u]+D[u][w]; for（i=;i<Gvexnum;++i） P[v][w][i]=P[v][w][i]; }//if }//ShortestPath_FLOYD 托普排序 拓扑序列设G=（VE）是一个具有n个顶点的有向图V中的顶点序列vv…vn称为一个拓扑序列当且仅当满足下列条件若从顶点vi到vj有一条路径则在顶点序列中顶点vi必在顶点vj之前 拓扑排序对一个有向图构造拓扑序列的过程称为拓扑排序 基本思想 （）从AOV网中选择一个没有前驱的顶点并且输出 （）从AOV网中删去该顶点并且删去所有以该顶点为尾的弧 （）重复上述两步直到全部顶点都被输出或AOV网中不存在没有前驱的顶点 返回《数据结构》考研复习精编 [] [] [] [] [] [] [] [] [] [] |
