单节点对所有最短路径----一个暂且认为的伪码

PAT-1003 试题地址：https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376

这个题真的非常良心，我恶补算法导论图论章节才想到这个方法，还未实现， 但记录下伪码：

在指定图$G<V,E>$为连通图，即任何节点$v_i{v}_j\in V$,有$v_i=>v_j$,权重函数$E->R$,假设图中不存在权值为负的环路， 则最短路径为一条无环路径。基于C++的内存模型，给出C++兼容伪码 思路：

//s为源点，d为目的点，G为图 FindAllShortestPath(s,d,G){ //运行一遍Dijkstra算法，所有<s,v>最短路径估计都记录在图中 Dijkstra(s,d,G); //为了缩小计算量，筛选边集 /**一开始的思路是先筛选节点集，不过先删边可以同时删节点，所以放弃开始的想法，先删边我们可以在后面看到**/ for(each edge in E){ if(w(u,v)+u.d>v.d){ /**经过Dijkstra算法所有节点存储的都是从源s到本节点最短路径长度， 如果存在经过u，v的最短路径，必然不会选直接边<u,v>,而是选某个更短路径。如果不存在经过u,v的最短路径，把该边删掉无害**/ delete this edge in E; } } //如此，删掉边之后，会导致某些点不可达 Q=DFS(s); for(each vertex in V){ if(vertex not in Q){ //删掉节点及相关边 delete this vertex and related edge; } } //剩下的节点必然是存在与某一最短路径呢？不一定。因为局部最优不等于全局最优 //接下来交给动态规划算法 dynamicPathSeeking(s,d,G,Path{only s}); }

接下来的分治的毫无亮点，就是从节点出发，进行路径决策，有两条原则：

其一：如果图一旦出现环路，就放弃这个决策。其二：路径累计值未到达目的节点，而大于等于最短路径预估。 那就写下个思路，这个算法是多项式算法没错，不过，复杂度真的不好办。 因为我实在找不出可以记录的重复计算过程。因为图的模式过于复杂，欲哭无泪。 <bool ,Path<vertex>> dynamicPathSeeking(s,d,G,Path<vertex>){ if(V-{s,d}.empty){ add d in path; return <true,path>; } else{ for(each vertex connected with s){ add vertex in path; if(path.weight>=d.d&&vertex!=d){ return <false,path> } else{ delete vertex in G.V; <tempbool,tempPath>=dynamicPathSeeking(vertex,d,G,path); if(tempbool){ if(tempPath consist d){ add path to G's shortest paths; }else{ return <true,path>; } }else{ return <false,path>; } } } } }

最后就是取出G中记录的所有最短路径。