当前位置：首页 > article >正文

4.3 最短路径问题：Dijkstra、Floyd

article 2025/1/7 9:39:41

4.3 最短路径问题：Dijkstra、Floyd

在图论中，最短路径问题是一种经典问题，它的目标是在给定的图中找到两个顶点之间的最短路径。在这一节，我们将会介绍两种最常用的解决最短路径问题的算法：Dijkstra算法和Floyd算法。

Dijkstra算法

Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻提出的一种用于在图中找到单源最短路径的算法，尤其是在权重图中。这个算法使用了广度优先搜索的思想，并且采用了优先队列的数据结构来迅速找到下一个最短的路径。

import java.util.*;

class Edge {
    int to, weight;

    public Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class Dijkstra {
    public void shortestPath(List<Edge>[] graph, int start) {
        int n = graph.length;
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int v = edge.to;
            if (dist[v] < edge.weight) continue;
            for (Edge e : graph[v]) {
                int to = e.to;
                int weight = e.weight;
                if (dist[v] + weight < dist[to]) {
                    dist[to] = dist[v] + weight;
                    pq.add(new Edge(to, dist[to]));
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            System.out.printf("Shortest distance from %d to %d: %d\n", start, i, dist[i]);
        }
    }
}

Floyd算法

Floyd算法（Floyd-Warshall算法）是一种解决任意两点之间的最短路径的问题的算法。与Dijkstra算法不同，Floyd算法能够处理有向图和负权重的边，但是不能处理存在负权重环路的图。

public class Floyd {
    public void shortestPath(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            System.arraycopy(graph[i], 0, dist[i], 0, n);
        }

        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] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                System.out.printf("Shortest distance from %d to %d: %d\n", i, j, dist[i][j]);
            }
        }
    }
}