求最短路径众所周知有Dijistra算法、Bellman-ford等,除了这些算法,用动态规划也可以求出最短路径,时间复杂度为O(n^2),
跟没有优化的Dijistra算法一样(优化后的Dijistra算法时间复杂度为O((m+n)lgn))。
左侧1-15表示前一个节点,最上面一行1-15表示后一个节点,记这个图的矩阵为P,那么P[0][1]==5表示节点0与节点1相连
,路径长度为5。那么我们如何利用动态规划来求解最短路径?
首先我们需要把整个问题转换成小的子问题,利用小的子问题的最优解求出整个问题的最优解。
我们的目的是求0-15之间的最短路径,由图可知与节点15相连的是结点14和节点13,假设我们已经求出0-13的最短路径的值D13和0-14的最短路径的值D14,
那么我们只需要比较D13+d(13-15)和D14+d(14-15)的大小就可以知道从哪个节点出发到节点15的路径最短。
按照这个思想一直往前推,推到节点0时结束,自然就求出了节点0-节点15的最短路径,这个思路是递归的,
如果用递归的方法,时间复杂度很高,当然你也可以用备忘录,记录已经计算过的值,我这里将递归转换成迭代。
我们先定义一个类class Node,里面存储节点的序号、从0到这个节点的最短路径的值、前一个节点的序号。
class node{ public int number; //value是指从0到这个节点总共要走多远,执行算法前将value的值初始化为无穷大 public int value; public int parent; }
最后将n[15].value打印出来就是最短路径的值,
再根据parent的值往前找就得到最短路径的解,当然这个例子有不同的路径的解,虽然值一样,我这里只给了一种。
class node { int value = Integer.MAX_VALUE; int parent; } public class Check { public static void main(String[] args) { node[] n = new node[16]; for (int i = 0; i < 16; i++) { n[i] = new node(); } int[][] array = { { 0, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 1, 3, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 8, 7, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 6, 8, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 3, 5, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 8, 4, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 2, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 6, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } }; for (int i = 0; i < 16; i++) { for (int j = i + 1; j < 16; j++) { if (array[i][j] != 0) { int temp = n[i].value + array[i][j]; if (temp< n[j].value) { // System.out.println(i+" "+j+" "+d+" "+n[j].value); n[j].value =temp; n[j].parent = i; } } } } int i = 15; System.out.print(15 + " "); while (i > 0) { System.out.print(n[i].parent + " "); // i--; i = n[i].parent; } } }