如何为有向图的Dijkstra最短路径算法添加路径追踪功能？

针对你提供的Dijkstra实现，有非常简便的修改方案——只需要维护一个前驱节点数组，记录每个顶点在最短路径上的前一个节点，之后通过回溯这个数组就能还原出从源点到任意顶点的完整最短路径。

核心修改步骤 #

• 添加前驱节点数组：在最短路径计算过程中，初始化一个数组记录每个顶点的前置节点，源点的前驱可设为自身或-1。
• 同步更新前驱节点：当某个顶点的最短距离被更新时，同步记录它的前驱为当前处理的顶点。
• 新增路径还原方法：通过回溯前驱数组，倒序拼接出完整路径后反转，得到从源点到目标点的正序路径。
• 修改打印逻辑：在输出距离的同时，打印对应的最短路径。

修改后的完整代码 #

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;

public class DijkstraMinHeap {
    static class Edge {
        int source;
        int destination;
        int weight;

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

    static class HeapNode {
        int vertex;
        int distance;
    }

    static class Graph {
        int vertices;
        LinkedList<Edge>[] adjacencylist;

        Graph(int vertices) {
            this.vertices = vertices;
            adjacencylist = new LinkedList[vertices];
            for (int i = 0; i < vertices; i++) {
                adjacencylist[i] = new LinkedList<>();
            }
        }

        public void addEdge(int source, int destination, int weight) {
            Edge edge = new Edge(source, destination, weight);
            adjacencylist[source].addFirst(edge);

            /**edge = new Edge(destination, source, weight);
            adjacencylist[destination].addFirst(edge); //for undirected graph*/
        }

        public void dijkstra_GetMinDistances(int sourceVertex) {
            int INFINITY = Integer.MAX_VALUE;
            boolean[] SPT = new boolean[vertices];
            // 新增：前驱节点数组，记录每个顶点的最短路径前置节点
            int[] predecessor = new int[vertices];
            Arrays.fill(predecessor, -1);
            predecessor[sourceVertex] = sourceVertex; // 源点前驱设为自身

            HeapNode[] heapNodes = new HeapNode[vertices];
            for (int i = 0; i < vertices; i++) {
                heapNodes[i] = new HeapNode();
                heapNodes[i].vertex = i;
                heapNodes[i].distance = INFINITY;
            }

            heapNodes[sourceVertex].distance = 0;

            MinHeap minHeap = new MinHeap(vertices);
            for (int i = 0; i < vertices; i++) {
                minHeap.insert(heapNodes[i]);
            }

            while (!minHeap.isEmpty()) {
                HeapNode extractedNode = minHeap.extractMin();
                int extractedVertex = extractedNode.vertex;
                SPT[extractedVertex] = true;

                LinkedList<Edge> list = adjacencylist[extractedVertex];
                for (Edge edge : list) {
                    int destination = edge.destination;
                    if (!SPT[destination]) {
                        int newKey = heapNodes[extractedVertex].distance + edge.weight;
                        int currentKey = heapNodes[destination].distance;
                        if (currentKey > newKey) {
                            decreaseKey(minHeap, newKey, destination);
                            heapNodes[destination].distance = newKey;
                            // 新增：更新当前顶点的前驱节点
                            predecessor[destination] = extractedVertex;
                        }
                    }
                }
            }
            // 修改：传入前驱数组打印路径
            printDijkstra(heapNodes, sourceVertex, predecessor);
        }

        public void decreaseKey(MinHeap minHeap, int newKey, int vertex) {
            int index = minHeap.indexes[vertex];
            HeapNode node = minHeap.mH[index];
            node.distance = newKey;
            minHeap.bubbleUp(index);
        }

        // 新增：通过前驱数组还原路径
        private List<Integer> getPath(int source, int target, int[] predecessor) {
            List<Integer> path = new LinkedList<>();
            // 源点到自身直接返回
            if (source == target) {
                path.add(source);
                return path;
            }
            // 不可达情况
            if (predecessor[target] == -1) {
                return null;
            }
            // 回溯前驱节点
            int current = target;
            while (current != source) {
                path.add(current);
                current = predecessor[current];
                // 防止异常循环（Dijkstra算法理论不会出现）
                if (current == -1) {
                    return null;
                }
            }
            path.add(source);
            Collections.reverse(path);
            return path;
        }

        // 修改：打印距离和路径
        public void printDijkstra(HeapNode[] resultSet, int sourceVertex, int[] predecessor) {
            System.out.println("Dijkstra's Algorithm: (using Adjacency List and Min Heap)");
            for (int i = 0; i < vertices; i++) {
                String distanceStr = resultSet[i].distance == Integer.MAX_VALUE ? "unreachable" : String.valueOf(resultSet[i].distance);
                List<Integer> path = getPath(sourceVertex, i, predecessor);
                String pathStr = path == null ? "unreachable" : path.stream().map(String::valueOf).collect(Collectors.joining(" -> "));
                System.out.printf("Node: %d | Distance: %s | Path: %s%n", i, distanceStr, pathStr);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("./vg1.txt"));
        printResult(br);
    }

    public static void printResult(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer((br.readLine()));
        int vertices = Integer.parseInt(st.nextToken());
        Graph graph = new Graph(vertices);

        int K = Integer.parseInt((st.nextToken()));
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            graph.addEdge(from, to, weight);
        }
        int source_vertex = 1;
        graph.dijkstra_GetMinDistances(source_vertex);
    }

    static class MinHeap {
        int capacity;
        int currentSize;
        HeapNode[] mH;
        int[] indexes; //will be used to decrease the distance

        public MinHeap(int capacity) {
            this.capacity = capacity;
            mH = new HeapNode[capacity + 1];
            indexes = new int[capacity];
            mH[0] = new HeapNode();
            mH[0].distance = Integer.MIN_VALUE;
            mH[0].vertex = -1;
            currentSize = 0;
        }

        public void display() {
            for (int i = 0; i <= currentSize; i++) {
                System.out.println(" " + mH[i].vertex + " distance " + mH[i].distance);
            }
            System.out.println("________________________");
        }

        public void insert(HeapNode x) {
            currentSize++;
            int idx = currentSize;
            mH[idx] = x;
            indexes[x.vertex] = idx;
            bubbleUp(idx);
        }

        public void bubbleUp(int pos) {
            int parentIdx = pos / 2;
            int currentIdx = pos;
            while (currentIdx > 0 && mH[parentIdx].distance > mH[currentIdx].distance) {
                HeapNode currentNode = mH[currentIdx];
                HeapNode parentNode = mH[parentIdx];

                indexes[currentNode.vertex] = parentIdx;
                indexes[parentNode.vertex] = currentIdx;
                swap(currentIdx, parentIdx);
                currentIdx = parentIdx;
                parentIdx = parentIdx / 2;
            }
        }

        public HeapNode extractMin() {
            HeapNode min = mH[1];
            HeapNode lastNode = mH[currentSize];
            indexes[lastNode.vertex] = 1;
            mH[1] = lastNode;
            mH[currentSize] = null;
            sinkDown(1);
            currentSize--;
            return min;
        }

        public void sinkDown(int k) {
            int smallest = k;
            int leftChildIdx = 2 * k;
            int rightChildIdx = 2 * k + 1;
            if (leftChildIdx < heapSize() && mH[smallest].distance > mH[leftChildIdx].distance) {
                smallest = leftChildIdx;
            }
            if (rightChildIdx < heapSize() && mH[smallest].distance > mH[rightChildIdx].distance) {
                smallest = rightChildIdx;
            }
            if (smallest != k) {
                HeapNode smallestNode = mH[smallest];
                HeapNode kNode = mH[k];

                indexes[smallestNode.vertex] = k;
                indexes[kNode.vertex] = smallest;
                swap(k, smallest);
                sinkDown(smallest);
            }
        }

        public void swap(int a, int b) {
            HeapNode temp = mH[a];
            mH[a] = mH[b];
            mH[b] = temp;
        }

        public boolean isEmpty() {
            return currentSize == 0;
        }

        public int heapSize() {
            return currentSize;
        }
    }
}

说明 #

修改后的代码运行时，会为每个顶点输出：

• 顶点编号
• 到源点的最短距离（不可达则显示unreachable）
• 对应的最短路径（不可达则显示unreachable）

内容的提问来源于stack exchange，提问作者Beka Bex