1、算法目标

计算指定顶点到其余各个顶点的最短距离！！！

2、算法的基本思想

  • 创建两个集合S和U，

集合S：代表已经访问过的顶点及起点到该顶点的距离；
集合U：代表还未访问过的顶点及到这些顶点的距离；

  • 具体思想：从出发顶点开始，不断从集合U中取出从当前顶点出发，距离较短的顶点作为新的访问顶点，加入已访问过的顶点集合S，不断更新循环，直至U集合为空。

02.jpg

3、具体步骤

  • step1：准备工作，获得各顶点以及其权重生成一个图；
  • step2：定义一个dijks类，实现当顶点加入集合S时的各个属性的更新；

dijks类的属性可以用三个数组来表示：
boolean isvisit[];//当前节点是否被访问：true代表已访问，false代表未访问
int pre[];//代表当前节点的前驱节点，例如pre[2]=0,代表索引2的顶点的上一个索引的顶点未0；
int dis[];//代表从出发顶点到当前顶点的最短路径；
dijks类定义的相关方法，当顶点加入集合S时，实现三大数组的更新：
method1：public djsArr(int len,int index)——指定出发顶点，初始化dijks类；
method2：isVisit(int index)——判断当前顶点是否被访问过，如果被访问过，则为true，否则为false；
method3：updateDis(int len，int index )——更新出发顶点到index顶点的距离
mehtod4：updatePre(int pre，int index)——更新下标为pre为顶点的前驱节点为index；
method5：getDis（int index）——返回出发顶点到index顶点的距离
★method6：updateIndex（）——更新index为最新的访问点
method7：addPath（i）——添加路径对应的下标

  • step3：指定一个出发顶点，开始实现dijkstra算法，
    1.    - 1、首先找到出发顶点，调用★update()方法实现更新当前顶点的前驱节点pre与路径dis。
    2.    - 2、遍历未访问过的顶点，找到从当前顶点开始的最短距离的顶点，作为新的访问点，调用updateIndex（）进行更新新的访问点，然后更新的访问点的前驱节点与路径，然后重复步骤2，直至遍历结束。

  • 关键方法：

    • method1：updateIndex（）

      /**
*  更新index顶点为新的访问点
*/
public  int  UpdateIndex(){
   int index=0,minLen=10000;
   for (int i = 0; i <dis.length ; i++) {
       if (isvisit[i]==false&&dis[i]<minLen){
           index=i;
           minLen=dis[i];
       }
   }
   //将新的访问点置为已访问。
   isvisit[index]=true;
   return  index;
}

    • method2：update（）

      /**
*  首先根据传入的出发顶点，更新pre前驱节点和出发顶点到各个顶点距离
* @param start 出发顶点的下标索引
*/
private void update(int start) {
   int minlen=0;
   for (int i = 0; i <weight[start].length; i++) {
       minlen=dijks.getDis(start)+weight[start][i];
       if (!dijks.isVisit(i)&&dijks.getDis(i)>minlen){
           dijks.addPath(i);
           dijks.UpdatePre(i,start);
           dijks.UpdateDis(minlen,i);
       }
   }
}