最短路径dijkstra算法java

Dijkstra算法是一种用于解决带权重图中单源最短路径问题的贪心算法。这里所谓的单源最短路径，就是指在图中找到一个顶点，使得从该顶点出发到其他所有顶点的路径长度最短。

Dijkstra算法的基本思路是：对于给定的起点，首先将其标记为已访问，并设置起点到起点自身的距离为0。然后，遍历该起点能够到达的所有节点，并计算它们到起点的距离。选择距离最短的节点，标记为已访问，并将该节点作为中间节点，继续遍历其能够到达的所有节点，并更新它们到起点的距离。重复这个过程，直到所有节点都被标记为已访问。

以下是Dijkstra算法的Java实现：

import java.util.*;

public class DijkstraAlgorithm {
    private static int[][] graph;
    private static int[] dist;
    private static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入图的大小和边的数量
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 初始化图
        graph = new int[n][n];
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            graph[u - 1][v - 1] = w;
            graph[v - 1][u - 1] = w;
        }

        // 输入起点和终点
        int start = scanner.nextInt() - 1;
        int end = scanner.nextInt() - 1;

        // 初始化距离数组和访问数组
        dist = new int[n];
        visited = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // 开始遍历
        for (int i = 0; i < n; i++) {
            // 找到当前未访问节点中距离起点最近的节点
            int minDist = Integer.MAX_VALUE;
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    u = j;
                }
            }
            if (u == -1) break;

            // 标记当前节点为已访问
            visited[u] = true;

            // 更新与当前节点相邻的节点的距离
            for (int v = 0; v < n; v++) {
                if (graph[u][v] > 0 && !visited[v] && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        // 输出结果
        System.out.println(dist[end]);
    }
}