图--最短路径(dijkstra)

图的其他知识

    我们日常生活中使用的高德，百度之类的导航，当输入起点与终点后总是能给出最短的可选路线。这正是图理论的一种实现。关于最短路径大致有两个方向：单源最短(从A到任意其它)和任意最短(任意两点)。本节来学习其中的一种即单源最短

实现方式

    挑选任一顶点(假设为A)作为起始点，从其可直达的路线中挑选最短，其对应的顶点(假设为B)与起始点连线合并更新后继续挑选最短直到挑选完所有顶点

    可直达：

    挑选最短：

        AB

    合并更新(可将两点视作同一点，实际是中间顶点)：

        挑选最短：

            ABE

实现算法

    迪杰斯特拉(Dijkstra)

    弗洛伊德(Floyd)

图解

    第一次，从A点出发从直达路径AB、AD、AE、AG中挑选最短路径AB，将AB合并后C点可直达，其余不变。此时A到B的最短路径为8

    第二次，从A点出发，将B点作为中间顶点，此时直达的路径除了第一次从A出发的AB(已被挑选)、AD、AE、AG外，经过B又存在新的直达路径ABC。此时由A到C由原来的不可到达(数学上称为无穷大的值)变为13(更新)，且此时D点可直达。此时最短路径分别为ABC和AE，我们挑选C点，此时A到C的最短路径为13

    第三次，从A点出发，将B、C点作为中间顶点，存在新的直达路径ABCD，由于ABCD为19<30，故覆盖原直达路径AD。此时A到D的最短路径为19。我们在直达中挑选最短的AE

    第四次，从A点出发，将E点作为中间顶点，存在新的直达路径AEF和AEG，挑选F点作为直达顶点，此时A点由不可到达到可到达F，则此时A到F的最短路径为22。我们在直达中挑选最短的ABCD

    第五次，从A点出发，将B、C、D点作为中间顶点，存在新的直达路径ABCDF，由于ABCDF为21<AEF，故覆盖原直达路径AEF。此时A到F的最短距离更新为21。我们在直达中挑选最短的AE

    第六次，从A点出发，将E点作为中间顶点，存在新的直达路径AEG，由于AEG为20<AG，故覆盖原直达路径AG，此时，由于所有顶点均已被挑选，故算法结束

    此时，从A点到所有顶点的最短距离如下

            AB:8

            AC:13

            AD:19

            AF:21

            AE:13

            AG:20

JavaScript代码实现

    使用邻接矩阵存储图

        1-定义一维数组，存储顶点；定义对象存储权值

        2-初始化图

        3-根据边与顶点的关系填充权值

    初始化

        1-定义辅助数组isHasFounds，记录从源点到各顶点是否已经找到了最短路径，该数组初始值除了源点外(源点到自身标记为1表示不需要求路径)均为0，标识尚未找到任一条最短路径（【1，0，0，0，0，0，0】）

        2-定义辅助数组minPathValues，记录已经查找到的最短路径值，那么与isHasFounds配合使用时即：isHasFounds[1]表示找到了最短路径AB，值为minPathValues[1]=0（【0，0，0，0，0，0，0】）

        3-定义数组origin，标识源点，数据的成员为源点的邻接点的权值，不存在邻接点的初始为无穷大（【0，8，∞，30，13，∞，32】）

    挑选最短的邻接弧

        使用双for循环在所有的顶点中查找与源点距离最短的边，即origin中的8是为最小，其对应的顶点为B

    比较更新

（AA:0  AB:8  AC:13  AD:19  AE:13  AF:21  AG:20）