dijkstra算法java

Dijkstra算法是一种解决单源最短路径的贪心算法，用于计算一个节点到其他所有节点的最短路径。

算法流程：

1. 创建一个数组dist，用于记录起点到每个节点的最短距离。

2. 创建一个visited数组，用于记录每个节点是否已经被访问过。

3. 将起点的dist值设置为0，其他节点的dist值设置为无穷大。

4. 重复以下步骤，直到所有节点都被访问：

a. 从未访问过的节点中选取dist值最小的节点作为当前节点。

b. 标记该节点为已访问。

c. 遍历该节点的所有邻居节点，更新它们的dist值。如果新的距离比原来的距离小，就更新dist数组。

5. 得到起点到每个节点的最短路径。

Java代码实现：

import java.util.Arrays;

public class DijkstraAlgorithm {
    private int n; // 节点个数
    private int[][] graph; // 图的邻接矩阵

    public DijkstraAlgorithm(int n) {
        this.n = n;
        graph = new int[n][n];
    }

    // 添加边
    public void addEdge(int u, int v, int w) {
        graph[u][v] = w;
        graph[v][u] = w; // 如果是有向图，去掉这行
    }

    // Dijkstra算法
    public int[] dijkstra(int start) {
        int[] dist = new int[n]; // 起点到各点的最短距离
        boolean[] visited = new boolean[n]; // 是否已访问

        // 初始化
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // 计算最短路径
        for (int i = 0; i < n - 1; i++) {
            int u = findMinDist(dist, visited);
            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        return dist;
    }

    // 找到未访问节点中距离最小的节点
    private int findMinDist(int[] dist, boolean[] visited) {
        int minDist = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < n; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    public static void main(String[] args) {
        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(5);
        dijkstra.addEdge(0, 1, 10);
        dijkstra.addEdge(0, 4, 5);
        dijkstra.addEdge(1, 2, 1);
        dijkstra.addEdge(1, 4, 2);
        dijkstra.addEdge(2, 3, 4);
        dijkstra.addEdge(3, 2, 6);
        dijkstra.addEdge(3, 0, 7);
        dijkstra.addEdge(4, 1, 3);
        dijkstra.addEdge(4, 2, 9);
        dijkstra.addEdge(4, 3, 2);

        int[] dist = dijkstra.dijkstra(0);

        for (int i = 0; i < dist.length; i++) {
            System.out.println("0到" + i + "的最短距离为：" + dist[i]);
        }
    }
}