用java实现迪杰斯特拉算法

下面是用Java实现Dijkstra算法的示例代码：

import java.util.*;

public class DijkstraAlgorithm {
    // 顶点个数
    private int V;

    public DijkstraAlgorithm(int v) {
        V = v;
    }

    // 找到最短路径的顶点
    private int findMinDistance(int[] distance, boolean[] visited) {
        int minDistance = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < V; i++) {
            if (!visited[i] && distance[i] < minDistance) {
                minDistance = distance[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    // 打印最短路径
    private void printPath(int[] parent, int j) {
        if (parent[j] == -1) {
            return;
        }
        printPath(parent, parent[j]);
        System.out.print(j + " ");
    }

    // 打印结果
    private void printSolution(int[] distance, int[] parent, int src) {
        System.out.println("顶点\t\t最短距离\t\t最短路径");
        for (int i = 0; i < V; i++) {
            if (i == src) {
                continue;
            }
            System.out.print(src + " -> " + i + "\t\t" + distance[i] + "\t\t\t" + src + " ");
            printPath(parent, i);
            System.out.println();
        }
    }

    // Dijkstra算法
    public void dijkstra(int[][] graph, int src) {
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[src] = 0;

        boolean[] visited = new boolean[V];
        int[] parent = new int[V];
        Arrays.fill(parent, -1);

        for (int count = 0; count < V - 1; count++) {
            int u = findMinDistance(distance, visited);
            visited[u] = true;

            for (int v = 0; v < V; v++) {
                if (!visited[v] && graph[u][v] != 0 && distance[u] != Integer.MAX_VALUE
                        && distance[u] + graph[u][v] < distance[v]) {
                    distance[v] = distance[u] + graph[u][v];
                    parent[v] = u;
                }
            }
        }

        printSolution(distance, parent, src);
    }

    public static void main(String[] args) {
        int[][] graph = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 },
                { 0, 5, 7, 9, 0 } };
        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(5);
        dijkstra.dijkstra(graph, 0);
    }
}

该代码实现了Dijkstra算法的主要逻辑，其中`dijkstra`方法是核心方法，用于计算最短路径。在该方法内部使用了一个`distance`数组来存储源顶点到各个顶点的距离，使用一个`visited`数组来记录当前已经找到最短路径的顶点，使用一个`parent`数组来记录每个顶点的前一个顶点，以便在最后打印最短路径时使用。

在`dijkstra`方法内部，首先将源顶点的距离设置为0，将所有其他顶点的距离设置为正无穷大。然后进入循环，每次找到距离源顶点最近的未访问过的顶点，将其标记为已访问，然后遍历其所有邻居顶点，更新它们到源顶点的距离和前一个顶点。最后在`printSolution`方法中打印最短路径和距离。

在main方法中，创建一个二维数组`graph`表示图的邻接矩阵，然后创建一个`DijkstraAlgorithm`对象并调用`dijkstra`方法计算最短路径。