简单图论：遍历所有最短路径

系统管理员 2023-06-15 11:14 17阅读 0赞

今天遇到了两道要求遍历所有最短路径的题，我一直做不对的原因竟是我把无向图当成了有向图，郁闷的要死。

解决遍历所有最短路径，其实思路很简单，首先通过经典算法\[各种算法，![Dijkstra,bellman,floyd][Dijkstra_bellman_floyd]求出最短路径的长度，然后就只能DFS来找寻起始点、终点一样，长度为最短路径长度的路径即可，在DFS中可以使用![Path\[\]][Path]数组来保存路径。

DFS时注意要剪枝，路径上已经走过的点不要重复走，可以用![Visited\[\]][Visited]来保存。

这里要注意的是，如果边的权均为正，那么DFS的效率还是挺高的，可以在大于最短路时直接剪掉

如果边权存在负值，DFS就剪不了那么多枝了...

基本的算法如下：

初始时使用DFS(起点,0)即可，其中D表示的是终点，可以作为全局变量，start表示起始点，整个图都使用二维数组来存的，不过转成表算法也差不多。

![ansdis][]表示的是之前求出来的最短路，而![shortnum][]统计最短路径的条数。

void DFS(int start, int dis)
    {
         int i,j;
         if(dis>ansdist) return;  //带负权则不可剪枝
         for(i=0;i<N;i++)
         {
             if(!Visited[i] && i!=start && Graph[start][i]!=Infinity)
             {
                 if(dis + Graph[start][i] > ansdist) continue; //带负权则不可剪枝
                 else if(i==D && dis+Graph[start][i]==ansdist)
                 {
                     Path[start]=i;
                     shortnum++;
                     //此时就可以把Path[]路径打印或存储
                 }
                 else
                 {
                     Visited[start]=true;
                     int temp=Path[start];
                     Path[start]=i;
                     DFS(i,dis+Graph[start][i]);
                     Visited[start]=false;
                     Path[start]=temp;
                 }
             }
         }
    }

[Dijkstra_bellman_floyd]: https://private.codecogs.com/gif.latex?Dijkstra%2Cbellman%2Cfloyd
[Path]: https://private.codecogs.com/gif.latex?Path%5B%5D
[Visited]: https://private.codecogs.com/gif.latex?Visited%5B%5D
[ansdis]: https://private.codecogs.com/gif.latex?ansdis
[shortnum]: https://private.codecogs.com/gif.latex?shortnum