問(wèn)題描述：

Description

給定n(n<=500)個(gè)頂點(diǎn),以及E(E<=10000)條邊，使用迪杰斯特拉算法計(jì)算頂點(diǎn)s到頂點(diǎn)t的最短路徑.

Input

第一行輸入T表示有T組數(shù)據(jù)。每組數(shù)據(jù)第一行輸入n、E、s、t，分別表示頂點(diǎn)數(shù)、邊數(shù)、頂點(diǎn)s以及頂點(diǎn)t. 接下來(lái)
輸入E行每行三個(gè)正整數(shù)u(1<=u<=n)、v(1<=v<=n)、w，表示頂點(diǎn)u到頂點(diǎn)v之間無(wú)向邊長(zhǎng)度w（可能有重邊）。

Output

輸出T行正整數(shù)，第i行表示第i組數(shù)據(jù)s到達(dá)t的最短路徑長(zhǎng)度。若s無(wú)法到達(dá)t國(guó)，輸出-1.

Sample Input

3
2 2 1 2
1 2 1
1 2 2
3 1 1 3
2 3 1
3 3 1 3
1 2 1
1 2 3
2 3 1

Sample Output

1
-1
2

問(wèn)題分析：

狄克斯特拉算法?是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有權(quán)圖中最短路徑問(wèn)題。 迪杰斯特拉算法主要特點(diǎn)是從起始點(diǎn)開(kāi)始，采用貪心算法的策略，每次遍歷到始點(diǎn)距離最近且未訪問(wèn)過(guò)的頂點(diǎn)的鄰接節(jié)點(diǎn)，直到擴(kuò)展到終點(diǎn)為止。

可以使用兩個(gè)數(shù)組，一個(gè)記錄是否已經(jīng)找到最短路徑，另一個(gè)用于記錄找到的最短路徑值，?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-434553.html

代碼示例：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

int n, m, s, t;
int h[N], e[M], w[M], ne[M], idx; // 鄰接表存儲(chǔ)圖
int dist[N]; // dist[i] 表示起點(diǎn)到 i 的最短距離
bool st[N]; // st[i] 表示 i 是否已經(jīng)確定了最短路

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; // 添加一條從 a 到 b 權(quán)值為 c 的邊
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist); // 將 dist 數(shù)組全部初始化為 INF，表示起點(diǎn)到所有點(diǎn)的距離都未知
    dist[s] = 0; // 起點(diǎn)到自身的距離為 0
    for (int i = 0; i < n; i++) { // 迭代 n 次，每次確定一個(gè)最短路
        int t = -1; // t 記錄還未確定最短路的點(diǎn)中，離起點(diǎn)最近的點(diǎn)
        for (int j = 1; j <= n; j++) // 找離起點(diǎn)最近的點(diǎn)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true; // 標(biāo)記 t 已經(jīng)確定了最短路
        for (int j = h[t]; ~j; j = ne[j]) { // 用 t 更新其他點(diǎn)的距離
            int k = e[j];
            if (dist[k] > dist[t] + w[j])
                dist[k] = dist[t] + w[j];
        }
    }
    if (dist[t] == INF) return -1; // t 不可達(dá)，返回 -1
    else return dist[t]; // 返回起點(diǎn)到 t 的最短距離
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m >> s >> t;
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c), add(b, a, c); // 添加一條無(wú)向邊
        }
        cout << dijkstra() << endl;
    }
    return 0;
}

運(yùn)行結(jié)果：

到了這里，關(guān)于貪心法——迪杰斯特拉算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！