Dijkstra算法 java实现

Dijkstra算法是一种贪心算法，用于计算带权有向图中的单源最短路径。该算法的核心思想是从起点开始，逐步扩展到距离起点更远的顶点，直到到达目标顶点为止。在执行过程中，维护一个距离起点最短的已知路径集合，每次找出未访问的节点中距离起点最近的一个节点，并将其加入已知路径集合中。

以下是Dijkstra算法的java实现：

import java.util.*;

public class DijkstraAlgorithm {
    private static final int NO_PARENT = -1;

    private void dijkstra(int[][] adjacencyMatrix, int startVertex) {
        int vertexCount = adjacencyMatrix.length;
        int[] shortestDistances = new int[vertexCount];
        boolean[] visited = new boolean[vertexCount];

        for (int i = 0; i < vertexCount; i++) {
            shortestDistances[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }

        shortestDistances[startVertex] = 0;

        int[] parents = new int[vertexCount];
        parents[startVertex] = NO_PARENT;

        for (int i = 1; i < vertexCount; i++) {
            int nearestVertex = -1;
            int shortestDistance = Integer.MAX_VALUE;
            for (int j = 0; j < vertexCount; j++) {
                if (!visited[j] && shortestDistances[j] < shortestDistance) {
                    nearestVertex = j;
                    shortestDistance = shortestDistances[j];
                }
            }
            visited[nearestVertex] = true;
            for (int k = 0; k < vertexCount; k++) {
                int edgeDistance = adjacencyMatrix[nearestVertex][k];
                if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[k])) {
                    parents[k] = nearestVertex;
                    shortestDistances[k] = shortestDistance + edgeDistance;
                }
            }
        }

        printSolution(startVertex, shortestDistances, parents);
    }

    private void printSolution(int startVertex, int[] distances, int[] parents) {
        int vertexCount = distances.length;
        System.out.print("Vertex\t Distance\tPath");
        for (int i = 0; i < vertexCount; i++) {
            if (i != startVertex) {
                System.out.print("\n" + startVertex + " -> ");
                System.out.print(i + " \t\t ");
                System.out.print(distances[i] + "\t\t");
                printPath(i, parents);
            }
        }
    }

    private void printPath(int currentVertex, int[] parents) {
        if (currentVertex == NO_PARENT) {
            return;
        }
        printPath(parents[currentVertex], parents);
        System.out.print(currentVertex + " ");
    }

    public static void main(String[] args) {
        int[][] adjacencyMatrix = {{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}};
        DijkstraAlgorithm dijkstraAlgorithm = new DijkstraAlgorithm();
        dijkstraAlgorithm.dijkstra(adjacencyMatrix, 0);
    }
}