图的最短路径——迪杰斯特拉算法

题目

小赛要去位于 A 市的小码家。小赛来到 A 市的车站，买了一张 A 市的地图，他发现这里的地形非常的复杂。A 市的街道一共有 N 个路口，M 条道路，每条道路连接着两个路口，并且有各自的长度。目前，小赛所在的车站位于编号为 1 的路口，而小码家所在的路口编号为 N，小赛准备打出租车去，当然，路程越小，付的钱就越少。问题摆在眼前：请帮助小赛寻找一条最短路径，使得他可以花最少的钱到达小码家。

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {

    static StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int m = nextInt();
        int[][] adj = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                adj[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 1; i <= n; i++) {
            adj[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int p1 = nextInt();
            int p2 = nextInt();
            int l = nextInt();
            adj[p1][p2] = adj[p2][p1] = l;
        }
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;
        boolean[] visited = new boolean[n + 1];
        Arrays.fill(visited, false);
        for (int i = 1; i <= n; i++) {
            int cur = getMinIndex(dist, visited);
            visited[cur] = true; // 标记访问过结点
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && adj[cur][j] != Integer.MAX_VALUE && adj[cur][j] + dist[cur] < dist[j]) {
                    dist[j] = adj[cur][j] + dist[cur];
                }
            }
        }
        System.out.println(dist[n]);
    }

    private static int getMinIndex(int[] dist, boolean[] visited) {
        int min = Integer.MAX_VALUE;
        int index = -1;
        for (int i = 1; i < dist.length; i++) {
            if (!visited[i] && dist[i] < min) {
                min = dist[i];
                index = i;
            }
        }
        return index;
    }

    static int nextInt() throws IOException {
        streamTokenizer.nextToken();
        return (int) streamTokenizer.nval;
    }

    static long nextLong() throws IOException {
        streamTokenizer.nextToken();
        return (long) streamTokenizer.nval;
    }
}