网站开发算固定资产,做搜狗网站优化排名,顺德微信网站建设,收录查询代码DP 这道题目还可以用动态规划解决。在图论中解决最短路径问题有Dijkstra算法和bellman-ford算法。这道题目也需要用到DP。所以先学习一下这两个算法的思想和区别。 两个算法比较 Dijstra算法用来解决单源最短路径问题。具体内容看[文章]
算法解决问题适用范围解决思路松…DP 这道题目还可以用动态规划解决。在图论中解决最短路径问题有Dijkstra算法和bellman-ford算法。这道题目也需要用到DP。所以先学习一下这两个算法的思想和区别。 两个算法比较 Dijstra算法用来解决单源最短路径问题。具体内容看[文章]
算法解决问题适用范围解决思路松弛对象Dijkstra算法单源最短路径权重是正的图贪心顶点bellman-ford算法单源最短路径图不可以有负权环路动态规划边
ps:虽然我也不明白为什么叫松弛。只知道是不断处理不断优化的对象。 之所以做比较是想明白这两个算法有什么区别。以及第二个算法的思想是怎么应用在本题目。 本题目的DP方案参考链接。 首先使用Floy算法计算任意两点之间的最短路径。接着使用递归方程dp[i][j] Math.min(dp[i][j],dp[包含u但是不包含v 的状态][u]dist[u][v])。
public class ShortestPathVisitingAllNodesDP {private int[][] dis new int[15][15];private int[][] dp new int[113][13];public int shortestPathLength(int[][] graph) {int N graph.length;for (int[] row: dis) Arrays.fill(row, N*N);for (int i0; iN; i) {for (int j0; jgraph[i].length; j) {int u i, v graph[i][j];dis[u][v] 1;}}floyd(N);return dp(N);}/*** Floy算法任意两点之间的最短距离* param n*/public void floyd(int n) {for(int k0; kn; k)for(int i0; in; i)for(int j0; jn; j)dis[i][j] Math.min(dis[i][j], dis[i][k]dis[k][j]);}private int dp(int n) {for (int[] row: dp) Arrays.fill(row, n*n);for (int i0; in; i)dp[1i][i] 0;for (int group1; group(1n); group)for (int u0; un; u)for (int v0; vn; v) {int src 1 u, dst 1 v;//group包含src但是不包含dstif ((group src)!0 (group dst)0 )dp[group|dst][v] Math.min(dp[group][u] dis[u][v], dp[group|dst][v]);}int minDis 0x3f3f3f3f;for (int i0; in; i)minDis Math.min(dp[(1n)-1][i], minDis);return minDis;}public static void main(String[] args){int[][] graph new int[4][];graph[0] new int[]{1,2,3};graph[1] new int[]{0};graph[2] new int[]{0};graph[3] new int[]{0};int r new ShortestPathVisitingAllNodesDP().shortestPathLength(graph);System.out.println(r);}
}代码 关于FLoyd算法的介绍参考文章。 用二维数组记录任意两点之间的距离。dis[i][j]表示从i节点到j节点的距离。如果这两点之间有边则dis的初始值是边的权重否则是无穷大。 如果要让两点之间例如ab的路程变短那只能引入第三点k。如果a-k-b的距离小于a-b的距离那就引入k。有时候可能需要引入不止一个节点才能找到ab之间的最短路径a-k1-k2…-b。每个顶点可能使得另外两个节点路程变短。 第二步如果允许在所有节点之间跨越节点1。如果dis[i][1]dis[1][j]lt;dis[i][j]dis[i][1]dis[1][j]lt;dis[i][j]dis[i][1]dis[1][j]dis[i][j],那么dis[i][j]dis[i][1]dis[1][j]dis[i][j]dis[i][1]dis[1][j]dis[i][j]dis[i][1]dis[1][j]。需要用两个for循环实现替换。 第三步如果允许在所有节点之间跨越节点1、2。如何做呢我们需要在只允许经过1号顶点时任意两点的最短路程的结果下再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]e[2][j]是否比e[i][j]要小。 第四步,进一步计算允许跨越节点123…一直到节点n。最后的代码就是
public void floyd(int n) {for(int k0; kn; k)for(int i0; in; i)for(int j0; jn; j)dis[i][j] Math.min(dis[i][j], dis[i][k]dis[k][j]);}
