代碼

import java.util.Scanner;
/**
 * 從鍵盤輸入一張圖状共，用Dijkstra算法求解指定兩點(diǎn)之間的距離谁帕，為了統(tǒng)一頂點(diǎn)編號(hào)也從0開始
 * 當(dāng)然還有一些地方可以用堆、鄰接表來(lái)優(yōu)化匈挖，這里關(guān)注點(diǎn)不在此。
 * @author XZP
 * 一組測(cè)試數(shù)據(jù)：
 6 9
 0 2
 0 1 1
 0 2 12
 1 2 9
 1 3 3
 2 4 5
 3 2 4
 3 4 13
 3 5 15
 4 5 4
 *
 */
public class Dijkstra {
    public static int[][] e;
    public static int[] dis;
    public static int INF = 99999;
    public static int M = 0; // 頂點(diǎn)個(gè)數(shù)
    public static int N = 0; // 邊的條數(shù)
    public static int v1, v2; // 第一個(gè)和第二個(gè)頂點(diǎn)的編號(hào)
    public static int v3, v4; // v3是起始頂點(diǎn)儡循，v4是終點(diǎn)
    public static int weight = INF; // 兩個(gè)頂點(diǎn)對(duì)應(yīng)邊的權(quán)重
    public static int[] book; // 用來(lái)標(biāo)記該點(diǎn)是否已經(jīng)更新過(guò)
    public static int target; // 用于存儲(chǔ)被選到的點(diǎn)
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            // 首先輸入頂點(diǎn)個(gè)數(shù)和邊的條數(shù)
            M = sc.nextInt();
            N = sc.nextInt();
            // 輸入要求距離之間的兩個(gè)頂點(diǎn)編號(hào)
            v3 = sc.nextInt();
            v4 = sc.nextInt();
            // 然后初始化
            init();
            // 所有的都初始化完畢之后開始為兩兩頂點(diǎn)之間輸入人為的權(quán)重值
            for (int i = 0; i < N; i++) { // N條邊所有要循環(huán)N次
                v1 = sc.nextInt();
                v2 = sc.nextInt();
                weight = sc.nextInt();
                e[v1][v2] = weight; // 注意頂點(diǎn)編號(hào)起點(diǎn)，要對(duì)應(yīng)一下
            }
            dijkstra(); // 求最短路徑誓琼，并將“松弛”結(jié)果更新dis數(shù)組
            System.out.println("頂點(diǎn)" + v3 + "到頂點(diǎn)" + v4 + "之間的最短路徑為：" + dis[v4]);
            for (int i = 0; i < M; i++) {
                System.out.print(dis[i] + " ");
            }
        }
    }
    public static void dijkstra() {
        initDis();
        for (int i = 0; i < M; i++) {
            // 每次選取還未標(biāo)記的剩余點(diǎn)中的離v3最近的點(diǎn)
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < M; j++) {
                if (book[j] == 0 && dis[j] < min && j != v3) {
                    min = dis[j];
                    target = j;
                }
            }
            book[target] = 1;
            // 對(duì)所有target的出邊進(jìn)行松弛
            for (int j = 0; j < M; j++) {
                if (dis[j] > dis[target] + e[target][j]) {
                    dis[j] = dis[target] + e[target][j];
                }
            }
        }
    }
    /**
     * 當(dāng)二維數(shù)組e有了確切值之后肴捉，需要初始化單源頂點(diǎn)v3到各個(gè)點(diǎn)之間的距離數(shù)組dis
     */
    public static void initDis() {
        // 初始化dis數(shù)組
        for (int i = 0; i < M; i++) {
                if (i == v3) {
                    dis[v3] = 0;
                    book[v3] = 1;
                } else {
                    dis[i] = e[v3][i];
                }
            }
    }
    public static void init() {
        // 初始化存儲(chǔ)邊的數(shù)組
        e = new int [M][M];
        // 初始化存儲(chǔ)頂點(diǎn)之間最小距離的數(shù)組dis
        dis = new int[M];
        // 初始化標(biāo)記數(shù)組
        book = new int[M];
        // 初始化邊數(shù)組的信息
        for (int i = 0; i < M; i++) {
            for (int j = 0;j < M; j++) {
                if (i == j) {
                    e[i][j] = 0; // 同一頂點(diǎn)之間的距離為0
                } else {
                    e[i][j] = INF; // 其他初始化為“無(wú)窮大”
                }
            }
        }
    }
}

幾點(diǎn)注意

• 根據(jù)稀疏度可以從存儲(chǔ)結(jié)構(gòu)上優(yōu)化
• 時(shí)間復(fù)雜度O(N^2)
• 不能求解負(fù)帶權(quán)邊的圖