使用java写一个迪杰斯特拉算法

在Java中，我们可以使用邻接矩阵或邻接表来实现Dijkstra最短路径算法。这里是一个基本的邻接矩阵版本的例子：

import java.util.*;

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE;

    // 图的邻接矩阵表示
    private int[][] graph;
    private int vertices; // 节点数

    public Dijkstra(int[][] matrix) {
        this.graph = matrix;
        this.vertices = matrix.length;
    }

    public void dijkstra(int startNode) {
        // 初始化距离数组和已访问数组
        int[] distances = new int[vertices];
        boolean[] visited = new boolean[vertices];

        Arrays.fill(distances, INF);
        distances[startNode] = 0;

        for (int i = 0; i < vertices - 1; ) {
            // 找到当前未访问且距离最小的节点
            int u = findMinDistance(distances, visited);

            if (visited[u]) {
                i++;
                continue;
            }

            visited[u] = true;

            // 更新所有从u可达节点的距离
            for (int v = 0; v < vertices; v++) {
                if (!visited[v] && graph[u][v] != 0 && distances[u] != INF &&
                        distances[u] + graph[u][v] < distances[v]) {
                    distances[v] = distances[u] + graph[u][v];
                }
            }
        }

        printSolution(distances);
    }

    private int findMinDistance(int[] distances, boolean[] visited) {
        int minDistance = INF;
        int minIndex = -1;

        for (int i = 0; i < vertices; i++) {
            if (!visited[i] && distances[i] <= minDistance) {
                minDistance = distances[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    private void printSolution(int[] distances) {
        System.out.println("Shortest path from node 0 to other nodes:");
        for (int i = 0; i < vertices; i++) {
            System.out.println("Node " + i + ": Distance = " + distances[i]);
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 0, 4, 0, 0, 0 },
                            { 4, 0, 8, 0, 0 },
                            { 0, 8, 0, 7, 0 },
                            { 0, 0, 7, 0, 9 },
                            { 0, 0, 0, 9, 0 } }; // 这里只是一个示例图，实际应用中可以自定义

        Dijkstra dijkstraAlg = new Dijkstra(matrix);
        dijkstraAlg.dijkstra(0); // 从第0个节点开始搜索
    }
}

这个程序首先初始化距离数组和已访问数组，然后在一个循环中不断找到未访问的节点并更新其相邻节点的距离，直到所有节点都被访问过。`findMinDistance`函数用于查找当前未访问且距离最小的节点。