图最短路径 #

dijkstra算法 #

求某一个指定点到其他全部点的最短路径

适用范围 #

有向图、无向图
不存在负权重
不存在

算法详情 #

初始化三个数组，dist[]和path[]和visit[]，dist数组用于保存指定点到其他点的最短路径，path保存指定点到i点的路径信息,visit保存访问的节点信息，对于已经访问过的节点，不再更新其最短路径信息。
- dist的初始化为邻接矩阵中指定点到其他点的距离信息，如果不可达，初始化为无穷大。
- path初始化为path[i]=origin，其中origin为指定点，不可达的点初始化为-1。
开始考虑加入其他的点的信息：
1. 选择dist数组中数值最小的一个元素min，且该点没有被考虑过，考虑该点。
2. 对于该点min，检查其可全部的未被考虑过的可达点（也就是没有被visit），对于这些获得的可达点 $P_i$ ，检查origin到 $P_i$ 是否存在新的最短路径，即dist[min]+edge[min][p_i]<dist[p_i]，同时更新path信息，p[p_i]=min。
3. 重复检查全部的点，直到全部被考察完毕。如果发现dist中已经找不到不是无穷大的点，也停止并退出
反推得到最短的路径信息。
1. 对于target点，其上一个点是p[target]
2. latest=p[target]，其上一个点是p[latest]
3. 一直到出现第一个origin停止

算法实现 #

int dijkstra(int origin,int target,int num){
  int[] dist=new int[num+1];
  int[] path=new int[num+1];
  int[] visit=new int[num+1];
  Arrays.fill(dist,Integer.MAX_VALUE);
  Arrays.fill(path,-1);
  for(int i=1;i<num+1;i++){
    if(i==origin){
        visit[i]=1;
        continue;
    }
    dist[i]=edge[origin][i];
    path[i]=origin;
  }
  int n=num-1;
  while(n>0){
    int min=Integer.MAX_VALUE;
    int minIndex=-1;
    for(int i=1;i< num+1;i++ ){
        if(visit[i]==0&&dist[i]<min){
            min=dist[i];
            minIndex=i;
        }
    }
    if(min==Integer.MAX_VALUE){
        break;
    }
    visit[minIndex]=1;
    for(int i=1;i<num+1;i++){
        if(edge[minIndex][i]==Integer.MAX_VALUE) continue;
        if(visit[i]==0&&dist[minIndex]+edge[minIndex][i]<dist[i]){
            dist[i]=dist[minIndex]+edge[minIndex][i];
            path[i]=minIndex;
        }
    }
    n--;
  }
  int minPathDist=dist[target];
  if(minPathDist==Integer.MAX_VALUE)return Integer.MAX_VALUE ;
  int latesNum=path[target];
  List<Integer> pathList=new ArrayList<>();
  pathList.add(target);
  pathList.add(latesNum)
  while(latesNum!=origin){
    latesNum=path[latesNum];
    pathList.add(latesNum);
  }
  pathList.add(origin);
}

Floyd算法 #

适用范围 #

不适用于负权环，因为负权环没有最短路