Dijkstra算法

邻接矩阵版

Dijkstra算法是一种用于查找图中两个节点之间的最短路径的算法。它由荷兰计算机科学家Edsger W. Dijkstra于1956年提出，并在1959年的论文中发表。该算法适用于带权有向图或无向图，只要图中的边权重都是非负数。

查看代码

import java.util.Arrays;

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE; // 无穷大

    public void dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dis = new int[n]; // 从起点到其他各点的距离
        boolean[] vis = new boolean[n]; // 标记已确定最短距离的顶点

        // 初始化距离数组和vis数组
        for (int i = 0; i < n; i++) {
            dis[i] = graph[start][i];
            vis[i] = false;
        }
        dis[start] = 0; // 到自身的距离为0
        vis[start] = true;

        for (int count = 1; count < n; count++) { // 总共需要n-1次迭代
            int mindis = INF, minIndex = -1;
            // 找到当前未访问过的、距离最近的顶点
            for (int v = 0; v < n; v++) {
                if (!vis[v] && dis[v] < mindis) {
                    mindis = dis[v];
                    minIndex = v;
                }
            }

            // 标记找到的顶点为已访问
            vis[minIndex] = true;

            // 更新与minIndex相邻的所有顶点的距离
            for (int v = 0; v < n; v++) {
                if (!vis[v] && graph[minIndex][v] != INF) {
                    dis[v] = Math.min(dis[v], dis[minIndex] + graph[minIndex][v]);
                }
            }
        }

        // 输出结果
        System.out.println("最短距离: " + Arrays.toString(dis));
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 0, 0, 0, 0, 0, 8, 0},
            {4, 0, 8, 0, 0, 0, 0, 11, 0},
            {0, 8, 0, 7, 0, 4, 0, 0, 2},
            {0, 0, 7, 0, 9, 14, 0, 0, 0},
            {0, 0, 0, 9, 0, 10, 0, 0, 0},
            {0, 0, 4, 14, 10, 0, 2, 0, 0},
            {0, 0, 0, 0, 0, 2, 0, 1, 6},
            {8, 11, 0, 0, 0, 0, 1, 0, 7},
            {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        new Dijkstra().dijkstra(graph, 0); // 以0号顶点为起点
    }
}

优先队列版

使用优先队列（Priority Queue）实现Dijkstra算法是一种更高效的方法，尤其是对于大型稀疏图。相比于基于邻接矩阵的传统实现，优先队列可以帮助我们更快地选择下一个待处理的顶点（即具有当前最短已知路径的顶点），从而减少算法的时间复杂度。

步骤

1. 初始化：

   • 创建一个优先队列，按照距离从小到大的顺序排序顶点。
   • 将所有顶点加入队列，并设置起始顶点的距离为0，其他顶点的距离为无穷大。
   • 创建一个数组或哈希表来存储每个顶点的当前最短距离。
   • 可选地，创建一个数组或哈希表来追踪每个顶点的前驱顶点。

2. 主循环：

   • 从优先队列中取出具有最小距离的顶点u。
   • 对于u的所有邻居v：
     • 计算通过u到达v的总距离。
     • 如果通过u到达v的距离小于之前记录的距离，则更新v的距离，并将v重新插入优先队列中（如果队列支持动态更新优先级，可以直接更新优先级）。

3. 终止条件：

   • 当优先队列为空时，算法结束。

代码实现

查看代码

import java.util.*;

public class DijkstraWithPriorityQueue {
    private static class Edge implements Comparable<Edge> {
        int v;
        int w;
        
        public Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.w, other.w);
        }
    }

    public void dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size();
        int[] dis = new int[n]; // 距离数组
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[start] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(start, 0)); // 添加起点

        while (!pq.isEmpty()) {
            Edge edge = pq.poll(); // 取出距离最小的顶点
            int u = edge.v;
            if (edge.w > dis[u]) continue; // 已经找到了更短的路径

            for (Edge next : graph.get(u)) {
                int v = next.v;
                int w = next.w;
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    pq.offer(new Edge(v, dis[v]));
                }
            }
        }

        // 输出结果
        System.out.println(Arrays.toString(dis));
    }

    public static void main(String[] args) {
        List<List<Edge>> graph = new ArrayList<>();
        // 构建图
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(new Edge(1, 4));
        graph.get(0).add(new Edge(7, 8));
        graph.get(1).add(new Edge(0, 4));
        graph.get(1).add(new Edge(7, 11));
        graph.get(1).add(new Edge(2, 8));
        graph.get(2).add(new Edge(1, 8));
        graph.get(2).add(new Edge(8, 2));
        graph.get(2).add(new Edge(3, 7));
        graph.get(3).add(new Edge(2, 7));
        graph.get(3).add(new Edge(4, 9));
        graph.get(3).add(new Edge(5, 14));
        graph.get(4).add(new Edge(3, 9));
        graph.get(4).add(new Edge(5, 10));
        graph.get(5).add(new Edge(3, 14));
        graph.get(5).add(new Edge(4, 10));
        graph.get(5).add(new Edge(6, 2));
        graph.get(6).add(new Edge(5, 2));
        graph.get(6).add(new Edge(7, 1));
        graph.get(6).add(new Edge(8, 6));
        graph.get(7).add(new Edge(0, 8));
        graph.get(7).add(new Edge(1, 11));
        graph.get(7).add(new Edge(8, 7));
        graph.get(7).add(new Edge(6, 1));
        graph.get(8).add(new Edge(2, 2));
        graph.get(8).add(new Edge(6, 6));
        graph.get(8).add(new Edge(7, 7));

        new DijkstraWithPriorityQueue().dijkstra(graph, 0); // 以0号顶点为起点
    }
}

时间复杂度

$O((V+E)logV)$，其中V是顶点数，E是边数。这是因为每次从优先队列中删除顶点的操作都需要O(log V)的时间。

Bellman-Ford算法

Bellman-Ford算法

Bellman-Ford算法是一种用来求解单源最短路径问题的算法，它可以处理含有负权重边的图，并且能够检测出图中是否存在负权重环。与Dijkstra算法相比，Bellman-Ford算法的适用范围更广，但其时间复杂度较高，为$O(|V|\ast |E|)$，其中$|V|$是顶点数，$|E|$是边数。

基本思想

Bellman-Ford算法的核心思想是通过逐步松弛（Relaxation）每条边，最终得到从源点到图中所有其他顶点的最短路径。具体来说，算法执行如下步骤：

1. 初始化：

   • 将源点到自己的距离设为0。
   • 将源点到其他所有顶点的距离设为无穷大（或一个非常大的数值）。

2. 松弛过程：

   • 对于图中的每一条边 (u, v)，重复进行|V| - 1轮松弛操作。对于每一轮，检查是否可以通过边 (u, v) 更新顶点 v 的距离。如果通过边 (u, v) 可以使顶点 v 的距离变得更小，则更新 v 的距离。
   • 这是因为经过每一轮松弛后，我们可以保证至多经过一轮中顶点数量减一的边的路径已经被正确地计算出来。

3. 检测负权重环：

   • 在进行了|V| - 1轮松弛之后，再进行一轮松弛。如果在这轮松弛过程中发现某个顶点的距离还可以被更新，那么说明图中存在至少一个负权重环，并且这个环可达于源点。

代码实现

查看代码

import java.util.*;

public class BellmanFord {
    public static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }

    public void bellmanFord(List<Edge> edges, int numVertices, int u) {
        int[] dis = new int[numVertices];
        
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[u] = 0;
        
        for (int i = 1; i <= numVertices - 1; i++) {
            for (Edge edge : edges) {
                int u = edge.u;
                int v = edge.v;
                int w = edge.w;
                if (dis[u] != Integer.MAX_VALUE && dis[u] + w < dis[v])
                    dis[v] = dis[u] + w;
            }
        }
        
        for (Edge edge : edges) {
            int u = edge.u;
            int v = edge.v;
            int w = edge.w;
            if (dis[u] != Integer.MAX_VALUE && dis[u] + w < dis[v]) {
                System.out.println("Graph contains negative w cycle");
                return;
            }
        }
        
        printSolution(dis, numVertices);
    }

    private void printSolution(int[] dis, int numVertices) {
        System.out.println("Vertex disance from u");
        for (int i = 0; i < numVertices; ++i)
            System.out.println(i + "\t\t" + dis[i]);
    }

    public static void main(String[] args) {
        int numVertices = 5;
        List<Edge> edges = new ArrayList<>();
        // Add edges
        edges.add(new Edge(0, 1, -1));
        edges.add(new Edge(0, 2, 4));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(1, 3, 2));
        edges.add(new Edge(1, 4, 2));
        edges.add(new Edge(3, 2, 5));
        edges.add(new Edge(3, 1, 1));
        edges.add(new Edge(4, 3, -3));

        BellmanFord bf = new BellmanFord();
        bf.bellmanFord(edges, numVertices, 0);
    }
}

SPFA

SPFA（Shortest Path Faster Algorithm）是对Bellman-Ford算法的一种改进，它利用了队列（Queue）来加速松弛过程，并且避免了重复松弛已经松弛过的边。SPFA可以显著提高算法在某些情况下的效率，特别是在具有大量边的图中，尽管其最坏情况的时间复杂度仍然是O(|V| * |E|)，但在实践中通常表现得更好。

基本思想

SPFA的主要思想是通过维护一个队列来跟踪当前正在处理的顶点，并且只对每个顶点进行一次入队操作。这样可以避免在Bellman-Ford算法中多次遍历相同的顶点。

SPFA算法的一个关键点在于，每个顶点最多只能进入队列一次，这有助于避免冗余的松弛操作，从而提高效率。

SPFA的具体步骤如下：

1. 初始化：

   • 将所有顶点的距离初始化为无穷大，除了源点的距离初始化为0。
   • 创建一个队列，并将源点加入队列。
   • 创建一个数组来标记哪些顶点已经在队列中。

2. 松弛过程：

   • 从队列中取出一个顶点u。
   • 对于顶点u的所有邻居v：
     • 检查是否可以通过边(u, v)更新顶点v的距离。
     • 如果可以更新，并且顶点v不在队列中，则将顶点v加入队列，并标记为已在队列中。

3. 终止条件：

   • 当队列为空时，算法结束。

代码实现

查看代码

import java.util.*;

public class SPFA {

    public static class Edge {
        int v;
        int w;

        public Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    public void spfa(List<List<Edge>> graph, int source) {
        int numVertices = graph.size();
        int[] dis = new int[numVertices]; // 存储最短距离
        boolean[] inQueue = new boolean[numVertices]; // 标记顶点是否在队列中
        Queue<Integer> queue = new LinkedList<>();

        // 初始化距离
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[source] = 0;
        queue.offer(source);
        inQueue[source] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            for (Edge edge : graph.get(u)) {
                int v = edge.v;
                int w = edge.w;

                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                    }
                }
            }
        }

        // 打印结果
        printSolution(dis, numVertices);
    }

    private void printSolution(int[] dis, int numVertices) {
        System.out.println("Vertex disance from Source");
        for (int i = 0; i < numVertices; ++i)
            System.out.println(i + "\t\t" + dis[i]);
    }

    public static void main(String[] args) {
        int numVertices = 5;
        List<List<Edge>> graph = new ArrayList<>();

        // 初始化邻接列表
        for (int i = 0; i < numVertices; i++) {
            graph.add(new ArrayList<>());
        }

        // 添加边
        graph.get(0).add(new Edge(1, -1));
        graph.get(0).add(new Edge(2, 4));
        graph.get(1).add(new Edge(2, 3));
        graph.get(1).add(new Edge(3, 2));
        graph.get(1).add(new Edge(4, 2));
        graph.get(3).add(new Edge(2, 5));
        graph.get(3).add(new Edge(1, 1));
        graph.get(4).add(new Edge(3, -3));

        SPFA spfa = new SPFA();
        spfa.spfa(graph, 0);
    }
}

代码解释

1. 初始化：将所有顶点的距离初始化为无穷大，除了源点的距离初始化为0。创建一个队列，并将源点加入队列。
2. 松弛过程：从队列中取出顶点u，并对其所有邻居进行松弛操作。如果通过u更新了邻居v的距离，并且v不在队列中，则将v加入队列。
3. 终止条件：当队列为空时，算法结束。