图-最短路径-在线编程-K6K4.com

最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。给定一个有向带权图，以及图中任意两个顶点，求两个顶点之间的最短路径。
约定：
（1）使用邻接矩阵表示图
（2）顶点编号从0开始
（3）最短路径唯一
（4）若两个顶点没有直接相连，权重值设置为-1

例如：
矩阵A的邻接矩阵表示为：
-1, 3,-1, 2,-1
-1,-1, 1,-1,-1
-1,-1,-1,-1, 1
-1,-1,-1,-1, 4
-1,-1,-1,-1,-1

顶点0->4的最短路径：0,1,2,4
顶点4->0的最短路径（有向性）：不存在，使用-1表示

输入、输出描述

输入：

A：有向图的邻接矩阵表示，若两个顶点没有直接相连，权重设置为-1
n：顶点的个数，顶点编号为：0，1，2...n-1
v1：起始顶点
v2：终点

输出：

从顶点v1到顶点v2之间的最短路径构成的数组，若不存在返回一个长度为1的数组，且元素值为-1

Example

输入：

A：
-1, 3,-1, 2,-1
-1,-1, 1,-1,-1
-1,-1,-1,-1, 1
-1,-1,-1,-1, 4
-1,-1,-1,-1,-1
n：5
v1：0
v2：4

输出：

0,1,2,4

修改

用Floyd算法计算图中两个顶点间的最短路径，可以先引入两个矩阵：dist、path，其中矩阵dist中的元素dist[i][j]表示点i到点j的最短距离；矩阵path中的元素[i][j]表示点i到点j经过了元素[i][j]记录的值所表示的点。

这里我们用到动态规划的思想：从任意节点i到任意节点j的最短路径不外乎两种可能，一是直接从i到j，二是从i经过若干个节点k到j。所以，我们假设dist[i][j]为节点i到节点j的最短路径的距离，对于每一个节点k，我们检查dist[i][k] + dist[k][j] < dist[i][j]是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置dist[i][j] =dist[i][k] + dist[k][j] ，path[i][j] = k，这样一来，当我们遍历完所有节点k，dist[i][j]中记录的便是i到j的最短路径的距离，path[i][j]记录的是点i到点j的前驱节点。

代码：

import java.util.*;

public class Main {
  public int[][] dist = null;//存储最短路径的长度
  public int[][] path = null;//存储最短路径的前驱节点
  public static final int max = Integer.MAX_VALUE;
  public ArrayList<Integer> list = new ArrayList<>();
  
  public void floyd(int[][] A,int n){
    //初始化
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        path[i][j] = -1;
        int edgeWeight = A[i][j];
        if(edgeWeight==-1){
          dist[i][j] = max;
        }else{
          dist[i][j] = edgeWeight;
        }
      }
    }
    
    for(int k=0;k<n;k++){
      for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
          if(dist[i][k]!=max && dist[k][j]!=max && dist[i][k]+dist[k][j]<dist[i][j]){
            dist[i][j] = dist[i][k]+dist[k][j];
            path[i][j] = k;
          }
        }
      }
    }
  }
  
  public void findPath(int i,int j){
    int k = path[i][j];
    if(k==-1)
      return;
    findPath(i,k);
    list.add(k);
    findPath(k,j);
  }
  
  public int[] solution(int[][] A,int n,int v1,int v2) {
    dist = new int[n][n];
    path = new int[n][n];
    floyd(A,n);
    list.clear();
    list.add(v1);
    findPath(v1,v2);
    list.add(v2);
    int[] pathTemp = null;
    if(dist[v1][v2] == max){
      pathTemp = new int[1];
      pathTemp[0] = -1;
    }else{
      int pathSize = list.size();
      pathTemp = new int[pathSize];
      for(int i=0;i<pathSize;i++){
        pathTemp[i] = list.get(i);
      }
    }
    return pathTemp;
  }
}