非线性数据结构--图的最短路径问题与动态规划问题的区别（一）

 

 

在数据结构里有两种类型的：一种是单源的最短路径问题，即从已知的指定节点出发；一种是任意两节点间的最短路径问题，即不明确起始节点，需要求出任意两点间的最短路径。显然后者的时间复杂度是必然会比前者大，因为后者的最终计算结果显然是包含前者的最终计算结果的。

常见的解决方案是：单源最短路径问题使用迪杰斯特拉算法求解，常规时间复杂度为o(n^2)，任意两节点的最短路径问题使用弗洛伊德算法求解,常规时间复杂度为O(n^3)。

 

 

package algorithm;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Project: texat
 * @Author: h
 * @Package: algorithm
 * @Version: V1.0
 * @Title: 关于图的动规
 * @Tag:
 * @Description:
 * 图的入门
 * 1.深度遍历；
 * 2.广度遍历
 * 图的动规算法：
 * 最短路径问题
 * 1.任意两点的最短路径；
 * 2.单源最短路径
 * @Date: 2020/6/14 23:23
 */
public class GraphSolution {

    private static final int MAX_VALUE = Integer.MAX_VALUE;
    private static boolean[] isAccessed;

    private static String deepForeach(int[][] edges, char[] nodes, int startNodeIndex) {
        StringBuilder stringBuffer = new StringBuilder();
        int[] edge = edges[startNodeIndex];
        stringBuffer.append(nodes[startNodeIndex]);
        isAccessed[startNodeIndex] = true;
        for (int i = 0; i < edge.length; i++) {
            if (i!= startNodeIndex && MAX_VALUE != edge[i] && !isAccessed[i]) { //没有自环路故不取本节点，且不取不可达节点和已访问节点
                stringBuffer.append(deepForeach(edges, nodes, i));
            }
        }
        return stringBuffer.toString();
    }

    private static String breadForeach(int[][] edges, char[] nodes, int startNodeIndex) {
        boolean[] isAccessed = new boolean[nodes.length];
        Queue queue = new Queue(nodes.length);
        queue.enQueue(startNodeIndex);
        isAccessed[startNodeIndex] = true;
        StringBuilder stringBuilder = new StringBuilder();
        while (!queue.isEmpty()) {
            int index = queue.deQueue();
            stringBuilder.append(nodes[index]);
            int[] edge = edges[index];
            for (int i = 0; i < edge.length; i++) {
                if (i != index && edge[i] != MAX_VALUE && !isAccessed[i]){
                    queue.enQueue(i);
                    isAccessed[i] = true;
                }
            }
        }
        return stringBuilder.toString();
    }

    private static class Queue {
        private int[] elems;
        private int maxCount;
        private int front;
        private int rear;

        public Queue(int maxCount) {
            this.maxCount = maxCount;
            this.elems = new int[maxCount];
            this.front = this.rear = 0;
        }

        public void enQueue(int e) {
            this.elems[this.rear ++] = e;
        }

        public int deQueue() {
            return this.elems[this.front ++];
        }

        public void clear() {
            this.elems = new int[this.maxCount];
            this.front = this.rear = 0;
        }

        public boolean isEmpty() {
            return this.rear == this.front;
        }
    }

    /**
     * 弗洛伊德算法求任意两点的最短路径
     * 状态转移方程：
     * min[i][j] = min{min[i][k] + min[k][j]}(k = 0, 1, .. n - 1, n为节点个数)
     * 关键在于：
     * 1.不按常规思路分类，降维分类：由于源节点和目的节点组成的二维表容易导向考虑二维上的遍历如何满足min[i][k]、min[k][j]满足相关定义，这样就会复杂化。
     * 事实上，视源节点、目的节点固定的情况下以其他参数做考虑（如中间节点），按引入的中间节点去分类，就从二维降低为一维去考虑，转化问题就显得容易考虑多了。
     * @param edges
     * @param nodes
     * @return
     */
    private static int[][] shortestPaths(int[][] edges, char[] nodes) {
        int[][] minPaths = new int[nodes.length][nodes.length];
        for (int i = 0; i < minPaths.length; i++) {
            for (int j = 0; j < minPaths[i].length; j++) {
                if (i == j) {
                    continue;
                }
                minPaths[i][j] = edges[i][j];
            }
        }

        for (int k = 0; k < nodes.length; k++) {
            for (int i = 0; i < nodes.length; i++) {
                for (int j = 0; j < nodes.length; j++) {
                    if (minPaths[i][k] == MAX_VALUE || minPaths[k][j] == MAX_VALUE) {
                        continue;
                    }
                    minPaths[i][j] = Math.min(minPaths[i][j], minPaths[i][k] + minPaths[k][j]);
                }
            }
        }
        return minPaths;
    }

    @SuppressWarnings("Duplicates")
    private static<T> int[] shortestPath(int[][] edges, T[] nodes, int srcNodeIndex) {
        if (nodes.length <= 0) {
            return new int[0];
        }
        if(nodes.length <= 1) {
            return new int[]{0};
        }
        boolean[] sureSet = new boolean[nodes.length];
        sureSet[srcNodeIndex] = true;
        //srcNode到其他节点的目标路径值数组
        int[] dis = new int[nodes.length];
        //初始化
        System.arraycopy(edges[srcNodeIndex], 0, dis, 0, dis.length);
        int min = srcNodeIndex == nodes.length - 1 ? srcNodeIndex - 1 : srcNodeIndex + 1;
        while (true) {
            for (int i = 0; i < dis.length; i++) {
                if (!sureSet[i] && dis[min] > dis[i]) {
                    min = i;
                }
            }
            sureSet[min] = true;
            //基于已确定最小值的当前节点min更新其他节点最小路径值
            boolean isAllPass = true;
            int unSure = -1;
            for (int i = 0; i < nodes.length; i++) {
                if (!sureSet[i]) {
                    unSure = i;
                    isAllPass = false;
                }
                if (!sureSet[i] && (edges[min][i] != MAX_VALUE && dis[min]!= MAX_VALUE) && dis[min] + edges[min][i] < dis[i]) {
                    dis[i] = dis[min] + edges[min][i];
                }
            }
            if (isAllPass) {
                break;
            }
            min = unSure;
        }
        return dis;
    }
    /**
     * 迪杰斯特拉算法求单源路径问题
     * 此算法以下实现可以优化：用小根堆维护dis数组，获取当前最小的路径
     * @param edges
     * @param nodes
     * @param srcNodeIndex
     * @return
     */
    private static int[] shortestPathsWithSingle(int[][] edges, char[] nodes, int srcNodeIndex) {
        boolean[] sureSet = new boolean[nodes.length];
        sureSet[srcNodeIndex] = true;
        //srcNode到其他节点的目标路径值数组
        int[] dis = new int[nodes.length];
        //初始化
        System.arraycopy(edges[srcNodeIndex], 0, dis, 0, dis.length);
        for (int ii = 0; ii < nodes.length;) {
            int min = 0;
            for (int i = 1; i < dis.length; i++) {
                if (i != srcNodeIndex && dis[min] > dis[i]) {
                    min = i;
                }
            }
            sureSet[min] = true;
            ii++;
            //基于已确定最小值的当前节点min更新其他节点最小路径值
            for (int i = 0; i < nodes.length; i++) {
                if (i != srcNodeIndex && (edges[min][i] != MAX_VALUE && dis[min]!= MAX_VALUE) && dis[min] + edges[min][i] < dis[i]) {
                    dis[i] = dis[min] + edges[min][i];
                }
            }
        }
        return dis;
    }

    public static void main(String[] strings) {
        String[] a = {
            "hot","dot","dog","lot","log","cog"
        };
        long[] powers = getPowers(3);
        System.out.println(Arrays.toString(powers));
        long l1 = stringHashCode(a[0]);
        long l2 = stringHashCode(a[1]);
        long l3 = stringHashCode(a[2]);
        long l4 = stringHashCode(a[3]);
        System.out.println(isLink(l1, l2, powers));
        System.out.println(isLink(l1, l4, powers));
        System.out.println(wordToWord("hot","log",a));
    }

}

注：关于连带的深度优先和广度优先，须说明一点必然规律：每学习一种数据结构，必然离不开它的遍历算法的学习，这是它的基础算法，显然易见的是上升到解决最短路径问题的算法正如前一篇所述官方给出的解决方案就包含了广度优先遍历的步骤。正如之前说的那样，对于找到阶段性最短路径，笔者的优化是使用小根堆，故单源路径问题可见有两种实现：穷举获取阶段性最短路径和用堆获取。

 

重点：适用范围（最优子结构、无后效性）、基本步骤（建模分析、得出最适用的状态转换方程、迭代遍历顺序）。

 动态规划相信大家经过前一系列的介绍都有一定了解了，重点注意状态转换方程的表达上:

　　　　　　　　　　　　　　　　　　　　　　f(i) = F(f(i - k0), f(i -k1),..)

 被迭代的状态f(i - k0),f(i - k1),...（参数）和迭代后的状态f(i)（结果）都表示对应某个集合范围内的最优解。虽然问题最终可能只要求得到某个指定范围对应的最优解，但毫无疑问，问题换成指定其他子集还是一样可以算出来。这就是最优子结构的一个特点。

 

 两者的区别：

对此我希望把最短路径问题分成两类问题回答：

1）对于弗洛伊德求解任意两点的最短路径问题，有迭代方程：

　　　　　　　　　　　　　　　　　　　　min[i][j] = min{min[i][k] + min[k][j]} , (k = 0, 1, 2, ...,n)

　　　其中，min[i][j]表示节点i和节点j之间的最短路径大小。该方程的得出是根据离散数学的图论知识中对图的一个定理：在一个连通图中任意两点i,j若有最短路径且经过若干个节点k0,k1,...,kn，则最短路径必然是由它经过的某个节点k和i之间的最短路径与k和j之间的最短路径组成。

　　　其证明，反证法显而易见：若不由它经过的任意一个节点k的由i和k之间的最短路径与k和j之间的最短路径组成，分三种情况：

　　　　（1）最短路径由i和k之间的最短路径与k和j之间的非最短路径组成，即min[i][j] = min[i][k] + p[k][j] > min[i][k] + min[k][j]，但因为i和j的最短路径min[i][j]必然不超过i和k与k和j的最短路径之和sum = min[i][k] + min[k][j]，否则最短路径min[i][j]就不符合最短路径的定义，所以有min[i][j] <= min[i][k] + min[k][j]，所以不成立； 

　　　　（2）最短路径由i和k之间的非最短路径与k和j之间的最短路径组成，与（1）同理；

　　　　（3）最短路径由i和k之间的非最短路径与k和j之间的非最短路径组成，与（1）、（2）同理。

　　　综上所述：该定理是成立的。

　　那么，这种解法是动态规划吗？对于该问题，换个角度说，其实就主要是这个迭代方程是不是状态转换方程来的。我们很清楚，所谓状态转换里的状态是指我们上文所说的最优子解，如果每个参与到该方程的参数（自变量）都可以作为一个最优子解，自然理应是一种状态转换方程。显然，min[i][k] 、min[k][j]都是最优子解，分别为i和k的最短路径、k与j的最短路径。从这个角度上说，弗洛伊德算法作为解决方案的最短路径问题求解确实是属于动态规划的一种方法。

 2）对于迪杰斯特拉算法求单源最短路径问题，有迭代方程：

　　　　　　　　　　　　　　　　　　　　min[i0][j] = min{min[i0][k] + e[k][j]}

　　　其中，i0为指定的单源节点，min[i0][j]表示i0到j的最短路径，min[i0][k]同理,e[k][j]为连通k与j的边。显然，该方程其实就是弗洛伊德算法的迭代方程的弱化版本，减少min[k][j]的计算，实则也符合单源最短路径问题的题意，因为我只要单源的最短路径即可。对于该方程中显然有e[k][j]不可以作为最优子解的，所以结合上述（1）的研讨是不属于动态规划的。