文章目錄

• 第一題：Dijkstra 算法求最短路徑
• • 題目描述
  • 輸入格式
  • 輸出格式
  • 輸入樣例
  • 輸出樣例
  • 解題思路&C++題解

目前創(chuàng)新互聯(lián)建站已為上千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、網(wǎng)站托管、服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、呼蘭網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。第一題：Dijkstra 算法求最短路徑 題目描述

給定一個(gè)有向圖 G = ( V , E ) G=(V,E) G=(V,E)，其中 V V V 為節(jié)點(diǎn)集合， E E E 為邊集合。每條邊 ( u , v ) (u,v) (u,v) 有一個(gè)權(quán)值 w ( u , v ) w(u,v) w(u,v)，表示從節(jié)點(diǎn) u u u 到節(jié)點(diǎn) v v v 的邊權(quán)。請(qǐng)你編寫(xiě)一個(gè)程序，計(jì)算出從節(jié)點(diǎn) s s s 到節(jié)點(diǎn) t t t 的最短路徑。

輸入格式

第一行包含三個(gè)整數(shù) n , m , s n,m,s n,m,s，分別表示節(jié)點(diǎn)數(shù)、邊數(shù)和起始節(jié)點(diǎn)。

接下來(lái) m m m 行，每行包含三個(gè)整數(shù) u , v , w u,v,w u,v,w，表示一條邊 ( u , v ) (u,v) (u,v) 的起點(diǎn)、終點(diǎn)和邊權(quán)。

最后一行包含一個(gè)整數(shù) t t t，表示終點(diǎn)。

輸出格式

如果存在從節(jié)點(diǎn) s s s 到節(jié)點(diǎn) t t t 的路徑，則輸出最短路徑的長(zhǎng)度。否則輸出 ? 1 -1 ?1。

約定：路徑的長(zhǎng)度為路徑上所有邊的權(quán)值之和。

輸入樣例

5 8 0
0 1 1
0 2 12
1 2 9
1 3 3
2 3 5
2 4 5
3 2 4
3 4 13
4

輸出樣例

8

解題思路&C++題解

此題可以使用 Dijkstra 算法來(lái)解決，Dijkstra 算法的時(shí)間復(fù)雜度為 O ( n 2 ) O(n^2) O(n2)，因此此題的時(shí)間復(fù)雜度為 O ( n 2 ) O(n^2) O(n2)。

Dijkstra 算法流程如下：

1. 初始化距離數(shù)組dis，將距離數(shù)組的所有元素賦值為無(wú)窮大，將起點(diǎn)的距離賦值為0。

2. 初始化一個(gè)未訪問(wèn)集合 v i s vis vis，表示所有節(jié)點(diǎn)是否已經(jīng)被訪問(wèn)過(guò)。

3. 將起點(diǎn)加入未訪問(wèn)集合 v i s vis vis。

4. 對(duì)于起點(diǎn)的每一個(gè)鄰居節(jié)點(diǎn) v v v，更新距離數(shù)組 d i s dis dis： d i s [ v ] = min ? ( d i s [ v ] , d i s [ u ] + w ( u , v ) ) dis[v]=\min(dis[v],dis[u]+w(u,v)) dis[v]=min(dis[v],dis[u]+w(u,v))。

5. 從未訪問(wèn)集合 v i s vis vis 中選擇一個(gè)距離最小的節(jié)點(diǎn) u u u，將其加入已訪問(wèn)集合中。

6. 對(duì)于節(jié)點(diǎn) u u u 的每一個(gè)鄰居節(jié)點(diǎn) v v v，更新距離數(shù)組 d i s dis dis： d i s [ v ] = min ? ( d i s [ v ] , d i s [ u ] + w ( u , v ) ) dis[v]=\min(dis[v],dis[u]+w(u,v)) dis[v]=min(dis[v],dis[u]+w(u,v))

7. 重復(fù)步驟 5 和 6 直到未訪問(wèn)集合為空。

時(shí)間復(fù)雜度： O ( n 2 ) O(n^2) O(n2)

空間復(fù)雜度： O ( n 2 ) O(n^2) O(n2)

下面是 c++ 代碼實(shí)現(xiàn)：

#include#include#include 

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m, s;
int g[N][N]; // 鄰接矩陣
int dis[N];  // dis[i] 表示從起點(diǎn)到 i 的最短路徑長(zhǎng)度
bool vis[N]; // vis[i] 表示節(jié)點(diǎn) i 是否已經(jīng)被訪問(wèn)過(guò)

// Dijkstra 算法
void dijkstra()
{// 初始化距離數(shù)組和未訪問(wèn)集合
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    dis[s] = 0;

    // 循環(huán)直到未訪問(wèn)集合為空
    while (true)
    {// 從未訪問(wèn)集合中選擇一個(gè)距離最小的節(jié)點(diǎn) u
        int u = -1, min_dis = INF;
        for (int i = 0; i< n; i++)
            if (!vis[i] && dis[i]< min_dis)
            {u = i;
                min_dis = dis[i];
            }

        // 如果未訪問(wèn)集合為空，則退出循環(huán)
        if (u == -1)
            break;

        // 將節(jié)點(diǎn) u 加入已訪問(wèn)集合
        vis[u] = true;

        // 更新節(jié)點(diǎn) u 的所有鄰居節(jié)點(diǎn)的距離
        for (int v = 0; v< n; v++)
            if (g[u][v] != INF)
                dis[v] = min(dis[v], dis[u] + g[u][v]);
    }
}

int main()
{cin >>n >>m >>s;

    // 初始化鄰接矩陣
    memset(g, 0x3f, sizeof g);
    while (m--)
    {int u, v, w;
        cin >>u >>v >>w;
        g[u][v] = w;
    }

    int t;
    cin >>t;

    // 調(diào)用 Dijkstra 算法
    dijkstra();

    // 輸出從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度
	if (dis[t] != INF)
		cout<< dis[t]<< endl;
	else
		cout<< -1<< endl;
	
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標(biāo)題：每日一練c++題目日刊|第九期：Dijkstra算法求最短路徑-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://weahome.cn/article/ddcgdh.html