求图的最短路径

求图的最短路径

初始化图

static final int n = 5;
public static void main(String[] args) {
    int[][] matrix = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = Integer.MAX_VALUE >> 1;
        }
        matrix[i][i] = 0;
    }
    matrix[0][1] = 10;
    matrix[1][0] = 10;
    matrix[0][3] = 30;
    matrix[3][0] = 30;
    matrix[0][4] = 100;
    matrix[4][0] = 100;
    matrix[1][2] = 50;
    matrix[2][1] = 50;
    matrix[2][3] = 20;
    matrix[3][2] = 20;
    matrix[2][4] = 10;
    matrix[4][2] = 10;
    matrix[3][4] = 60;
    matrix[4][3] = 60;
}

BFS

只能求无权图的最短路径

//求单源最短路径BFS
   //只能求无权图的最短路径
   public static int[] bfs(int[][] matrix, int src, int n){
       int[] dis = new int[n];
       Arrays.fill(dis, Integer.MAX_VALUE);
       dis[src] = 0;
       boolean[] visited = new boolean[n];
       visited[src] = true;
       Deque<Integer> queue = new ArrayDeque<>();
       queue.offer(src);
       while (!queue.isEmpty()){
           int cur = queue.poll();
           //求cur的临边
           for(int i = 0; i < n; i++){
               if(!visited[i] && matrix[cur][i] != 0){
                   dis[i] = dis[cur] + 1;
                   queue.offer(i);
                   visited[i] = true;
               }
           }
       }
       return dis;
   }

dijkstra

不能存在负权路径

//求单源最短路径dijkstra
//不能存在负权路径
public static int[] dijkstra(int[][] matrix, int src, int n){
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Set<Integer> set = new HashSet<>(n); //记录已经找到最短路径的顶点
    set.add(src);
    for(int i = 0; i < n; i++){
        dist[i] = matrix[src][i];
    }
    while (set.size() < n){
        int minDist = Integer.MAX_VALUE;
        int minIndex = -1;
        for(int i = 0; i < n; i++){
            if(!set.contains(i) && dist[i] < minDist){
                minDist = dist[i];
                minIndex = i;
            }
        }
        //当前顶点已经确定了最短路径
        set.add(minIndex);
        //更新到其他节点的最短路径
        for(int i = 0; i < n; i++){
            if(!set.contains(i) && dist[minIndex] + matrix[minIndex][i] < dist[i]){
                dist[i] = dist[minIndex] + matrix[minIndex][i];
            }
        }

    }
    return dist;
}

floyd

要求不存在负权回路

//floyd算法
//要求不存在负权回路
public static int[][] floyd(int[][] matrix, int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
            }
        }
    }
    return Arrays.copyOf(matrix, n);
}