找回密码
 立即注册
软件设计/软件工程 2022-05-02 212 0star收藏 版权: . 保留作者信息 . 禁止商业使用 . 禁止修改作品
【题意】给定一个有N(N<=100)个节点的有向图,求不相交的最短路径的个数(两条路径没有公共边)。 【思考】首先用Floyd求最短路径,将最短路径上的边加入到网络流中,保证从s->t的一个流一定是最短路径,这样也保证了网络 流动建模是正确的性。 【求最短路径上的边】满足最优子结构的性质:(i,j)是最短路径上的边当且仅当dist[s][i] + edge[i][j] + dist [j] [t] = dist[s][t]。 起初,我以为 dist[s][j] = dist[s][i] + edge[i][j] 就可以了,但这显然是错误的。 这只是满足点 i 到点 s 是最短路径,但不保证点 j 到点 t 也是最短路径,自然也不保证 (i, j) 是最短路径上的边 .

([question meaning] given a directed graph with n (n < = 100) nodes, find the number of disjoint shortest paths (two paths have no common edge). [thinking] first, use Floyd to find the shortest path and add the edge on the shortest path to the network flow to ensure that a flow from S - > t must be the shortest path, which also ensures the correctness of network flow modeling. [find the edge on the shortest path] satisfies the properties of the optimal substructure: (I, J) is the edge on the shortest path if and only if dist [S] [i] + edge [i] [J] + dist [J] [t] = dist [S] [t]. At first, I thought dist [S] [J] = dist [S] [i] + edge [i] [J], but it was obviously wrong. This only satisfies that point I to point s is the shortest path, but it does not guarantee that point J to point t is also the shortest path. Naturally, it does not guarantee that (I, J) is the edge on the shortest path
)





上一篇:静态库和动态库详解(部分参考他人)
下一篇:比较SHELL里面的大小