图：由点“Vertex”和边“Edge ”组成，且图分为有向图和无向图(本文讨论有向图)，之前做毕业设计的时候研究“多谱流形聚类算法”的时候有研究“Graph”。高维数据的聚类就涉及到Graph Cut算法，想象数据为欧式空间的点，数据与数据之间呈现这样或那样的联系，数据就是点，他们的联系由边来决定。PS：本次学习与聚类算法无关，聚类问题具体见之前写的博客。

 

     论：构建好了目标对象以及目标对象的关系，接下来的大头与研究的目的有关。比如，图论最广泛的应用之一：社交网络。我与张三是好朋友，那么我跟张三之间就有一个Edge来表示我俩之间的联系，张三与李四是好朋友，那张三和李四之间也有一个Edge来连接。如果我和李四之间没关系，那么我要想联系李四就需要通过联系张三再通过张三来和李四产生联系。一来二往，我和李四熟了，这时候我跟李四之间也有了Edge，这个时候我联系李四的方式就不止一种了，比如我既可以通过张三联系李四，也可以直接联系李四，至于选择哪种联系方式，而这个选择的过程中就涉及到你和张三的关系好坏程度、你与李四的好坏程度以及李四和张三的好坏程度，这种好坏程度在Graph中一般称为“权重”，权值为正关系好，权值为负关系差，再言之，关系这种东西是以自我为中心，比如我认为我和张三的关系是很好，但张三不认为我跟他的关系很好，这里就涉及到“有向图”。而今天讨论的“论”的目标为最短路径问题。

 

    解决最短路径问题的方法有很多种，本文主要探讨Dijkstra最短路径算法，通过阐述算法过程，实现简单Dijkstra算法，来对最短路径问题有一个比较深刻的了解。其次，我们知道JAVA作为面向对象的高级语言，有很多的轮子，我在谷歌搜了半天发现文档比较友好且算法和可视化都比较良好的开源轮子，分别是：JGraphT和GraphStream，这里只讨论JGraphT的调用（因为这个轮子的说明文档很nice ^$^）。

 

     Dijkstra算法流程

  1. 初始化：称给定的初始节点为根节点，给每一个节点设置设定初始化的距离（距离根节点），其中，根节点的距离为0（与自身的距离当然是0），其他所有节点与根节点的距离都是无穷大（不同场景下的距离可取不同的值，如计算机中一般取整型的最大值）；创建两个集合，一个集合用于收集已访问节点，另外一个集合收集待访问节点。

  2. 循环：对当前节点，重新计算根节点与所有邻接点的暂时距离，将这个新计算的暂时距离与邻接节点的当前距离进行比较取这两个距离中较小的值去更新邻接点的距离。比如当前节点为A,A有一个邻接点B，其中根节点为O；若A的当前距离为W(O,A)=6，B的当前距离为W(O,B)=10，A与其邻接点B的距离为distance(A,B)=2。则因为根节点O与A的邻接点B的暂时距离distance(O,B)等于W(O,A)+W(A,B)=6+2=8<W(O,B)，因此W(O,B)=distance(O,B)=8，以此类推，若W(O,B)<distance(O,B)，则W(O,B)的值不变。

  3. 更新集合：当我们完成前面的根节点与当前节点的所有邻接点的距离更新，将当前节点添加到已访问集合中，并将当前节点从待访问队列中取出。

  4. 循环条件：循环的终止条件为访问到目的节点D（求指定的OD节点之间的最短路径）或当前节点的左右邻接点中的距离最小为无穷大，否则就挑选距离最小的那个邻接点作为当前节点进入步骤2的循环。

 

     这里，我并不贴大量代码演示算法流程，只是做一个对比，讨论一下Dijkstra算法中的算法复杂度的提升上这么一个渐进的过程。

 

     下图图1来自于维基百科的

网友评论