国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<span id="kdab4"></span>

<span id="kdab4"></span>

第三章搜索與圖論（二）——最短路問題

2年前作者：.SacaJawea分類：Toy博客閱讀(35)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了第三章搜索與圖論（二）——最短路問題。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

源點(diǎn)表示起點(diǎn)，匯點(diǎn)表示終點(diǎn)
第三章搜索與圖論（二）——最短路問題,AcWing算法課課程記錄,圖論

第三章搜索與圖論（二）——最短路問題,AcWing算法課課程記錄,圖論

一些認(rèn)識：
m和

n^2

一個級別是稠密圖，m和n一個級別是稀疏圖
最短路問題不區(qū)分有向圖與無向圖，因?yàn)闊o向圖是一種特殊的有向圖，能解決有向圖的最短路問題，就能解決無向圖的最短路問題

單源最短路

起點(diǎn)確定，終點(diǎn)是除起點(diǎn)外的其他點(diǎn)
默認(rèn)n表示點(diǎn)數(shù)，m表示邊數(shù)

所有邊權(quán)為正數(shù)

樸素Dijkstra O( $n^2$ )，和邊數(shù)無關(guān)，用于稠密圖
堆優(yōu)化版Dijkstra O(mlogn) m = $n^2$ ，用于稀疏圖

邊權(quán)存在負(fù)數(shù)

Bellman-Ford O(nm)
SPFA O(m)，最壞O(nm)，是Bellman-Ford的優(yōu)化

樸素Dijkstra

基于貪心思想，每次選擇距離源點(diǎn)最近的點(diǎn)

維護(hù)一個s集合，存儲已經(jīng)確定最短路徑的點(diǎn)
一開始該集合中只有源點(diǎn)，不斷地將點(diǎn)加入到s集合中，直到圖中所有點(diǎn)都屬于s集合，最短路求解結(jié)束

如何將點(diǎn)加入s集合？

遍歷圖中不屬于s的點(diǎn)，選擇其中與源點(diǎn)距離最小的點(diǎn)加入s
對于此時不屬于s的點(diǎn)，用新加入s的點(diǎn)嘗試更新其他點(diǎn)的最短距離

重復(fù)以上兩個步驟，直到圖中所有點(diǎn)都屬于s
如何用代碼實(shí)現(xiàn)？
dis數(shù)組存儲每個點(diǎn)與源點(diǎn)的最短距離，初始化：源點(diǎn)到源點(diǎn)的距離為0
g數(shù)組為鄰接矩陣，存儲圖中每條邊的權(quán)值（若是稀疏圖則使用鄰接表）
vt數(shù)組用來維護(hù)s集合，存儲該點(diǎn)是否在s中的bool值

初始化dis[源點(diǎn)的編號] = 0, dis[其他點(diǎn)] = +∞
遍歷dis數(shù)組中不屬于s的點(diǎn)，選擇其中與源點(diǎn)距離最短的點(diǎn)加入s
根據(jù)新加入s的點(diǎn)，更新dis數(shù)組中其他不屬于s的點(diǎn)，假設(shè)新加入點(diǎn)的編號為x，`dis[y] = min(dis[y], dis[x] + g[x][y])
重復(fù)2，3兩個步驟，直到所有點(diǎn)屬于s

第三步中，對于已經(jīng)確定最短路徑的點(diǎn)（屬于s中的點(diǎn)），需要根據(jù)該點(diǎn)更新其他不屬于s中的點(diǎn)。此時進(jìn)行操作dis[y] = min(dis[y], dis[x] + g[x][y])，其實(shí)不需要特別要求該點(diǎn)不屬于s，因?yàn)閷儆趕的點(diǎn)已經(jīng)確定了最短距離，不論是否進(jìn)行min操作都不影響已經(jīng)確定的最短距離。所以在min操作之前判斷該點(diǎn)是否屬于s的操作是無關(guān)緊要的

模板：

bool vt[N];
int dis[N], g[x][y];

void dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    
    for (int i = 0; i < n; ++ i )
    {
        int x = -1;
        for (int j = 1; j <= n; ++ j)
            if (!vt[j] && (x == -1 || dis[j] < dis[x])) 
                x = j;

        vt[x] = true; // 從不屬于s的點(diǎn)中選擇距離源點(diǎn)最近的點(diǎn)
        for (int y = 1; y <= n; ++ y) // 用新加入的點(diǎn)更新其他點(diǎn)
            dis[y] = min(dis[y], dis[x] + g[x][y]);
    }
}

外循環(huán)迭代n次，每次選擇與源點(diǎn)距離最近的點(diǎn)放入集合中，集合中的點(diǎn)為已經(jīng)確定最短距離的點(diǎn)。迭代n次后，圖中所有點(diǎn)都進(jìn)入了s集合，即確定了所有點(diǎn)的最短距離
每一次迭代要做的事：

在不屬于s中的點(diǎn)中，找到與源點(diǎn)距離最近的點(diǎn)
用該點(diǎn)更新其他（不屬于s的）點(diǎn)

堆優(yōu)化版Dijkstra

用堆優(yōu)化樸素Dijkstra算法，時間復(fù)雜度可以達(dá)到O(mlogn)
若手寫一個支持修改任意位置的堆，空間復(fù)雜度為O(n)
若使用優(yōu)先隊(duì)列，空間復(fù)雜度將達(dá)到O(m)，存儲稠密圖比較浪費(fèi)空間

樸素Dijkstra算法中，在不屬于s的點(diǎn)中，找距離源點(diǎn)最近的點(diǎn)，時間復(fù)雜度為O(n)
外循環(huán)需要迭代n次，所以總得時間復(fù)雜度為O( $n^2$ )，這是樸素Dijkstra算法的效率瓶頸
用堆結(jié)構(gòu)對樸素算法進(jìn)行優(yōu)化，我們能以O(1) 的時間取出距離源點(diǎn)最近的點(diǎn)，不過代價(jià)就是提高了空間復(fù)雜度，從O(n) 提高到了O(m)。以及每次維護(hù)堆時，時間復(fù)雜度為O(logn)

同時，若使用鄰接矩陣存儲邊，用新加入的點(diǎn)更新其他點(diǎn)時，時間復(fù)雜度為O(n)，總的時間復(fù)雜度為O( $n^2$ )。也是一個瓶頸，不過很好解決，用鄰接表存儲邊，總的時間復(fù)雜度為O(m)

而使用鄰接表存儲，不用考慮重邊問題。鄰接矩陣只能存儲兩點(diǎn)間的一條邊，所以要選擇重邊中最小的邊

代碼如何實(shí)現(xiàn)？
用優(yōu)先隊(duì)列存儲pair，first為點(diǎn)到源點(diǎn)的距離，second為點(diǎn)的編號
由于優(yōu)先隊(duì)列無法修改元素，所以圖中的每條邊都會進(jìn)入一次優(yōu)先隊(duì)列，此時存在冗余且無效的數(shù)據(jù)
具體情況是：隊(duì)列中存在second相同的pair，此時first較大的pair為無效數(shù)據(jù)。但我們無法刪除任意位置的pair，只能刪除堆頂?shù)?code>pair。所以取出堆頂元素時需要判斷該pair的second是否已經(jīng)在s中（最短距離是否已經(jīng)確定）
若已經(jīng)在s中，說明不需要進(jìn)行接下來的操作（加入s和用該點(diǎn)更新其他點(diǎn)），所以此時直接continue

模板：

typedef pair<int, int> PII;

int h[N], e[N], ne[N], w[N], idx = 1;
priority_queue<PII, vector<PII>, greater<PII>> q;
int dis[N];
bool vt[N];

void dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    q.push({ 0, 1 }), dis[1] = 0;
    
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        
        int x = t.second, d = t.first;
        if (vt[x]) continue;
        vt[x] = true;
        
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (!vt[y] && d + w[i] < dis[y])
            {
                dis[y] = d + w[i];
                q.push({ dis[y], y });
            }
        }
    }
}

Bellman Ford算法

暴力美學(xué)

用于處理負(fù)權(quán)邊
存儲邊的結(jié)構(gòu)沒有要求，可以用簡單的結(jié)構(gòu)體存儲

struct Edge
{
	int x, y, w;
}edges[M];

循環(huán)n次，每次都遍歷所有邊
遍歷某條邊時，對其進(jìn)行松弛操作：dis[y] = min(dis[y], dis[x] + w[i])，其中x是當(dāng)前邊的起點(diǎn)，y是當(dāng)前邊的終點(diǎn)，w[i]是當(dāng)前邊的權(quán)重
每次的松弛操作其實(shí)是在嘗試更新dis[y]，而更新依賴于dis[x]。若dis[x]不是無窮大，而是被其他松弛操作更新了，那么dis[y]也可以被當(dāng)前松弛操作更新

外循環(huán)與dis數(shù)組的關(guān)系：若循環(huán)進(jìn)行了k次，dis數(shù)組存儲從源點(diǎn)開始走，不超過k條邊，遞達(dá)其他點(diǎn)的最短距離

若存在負(fù)環(huán)，則最短路不一定存在（負(fù)環(huán)與源點(diǎn)和目標(biāo)點(diǎn)不連通時則最短路存在）
用Bellman-Ford判斷負(fù)環(huán)：
第n次外循環(huán)時，若更新了dis數(shù)組，說明某條最短路中有n條邊，即n+1個點(diǎn)，根據(jù)抽屜原理，該圖存在負(fù)環(huán)
但Bellman-Ford的時間復(fù)雜度較高，一般用SPFA解決負(fù)環(huán)問題

三角不等式：dis[y] <= dis[x] + w

串聯(lián)問題：每次對所有邊進(jìn)行松弛操作時，應(yīng)該基于上一次對所有邊進(jìn)行松弛操作后的狀態(tài)。什么意思呢？對所有邊進(jìn)行了一次松弛操作后，我們要備份此時的dis數(shù)組，作為上一次的狀態(tài)保存
若不備份dis數(shù)組，而直接進(jìn)行松弛操作。修改dis數(shù)組的某些數(shù)據(jù)后，此時的dis數(shù)組不再是上一次對所有邊進(jìn)行松弛操作后的狀態(tài)，基于這個狀態(tài)進(jìn)行松弛操作得到的結(jié)果多半是錯誤的

串聯(lián)問題與dp狀態(tài)壓縮導(dǎo)致的問題類似

模板：

struct Edge
{
	int x, y, w;
}edges[M];

int dis[N], bup[N];
void bellman_ford()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    for (int i = 0; i < k; ++ i )
    {
        memcpy(bup, dis, sizeof(dis));
        for (int j = 0; j < m; ++ j )
        {
            auto t = edges[j];
            dis[t.y] = min(dis[t.y], bup[t.x] + t.w);
        }
    }
}

SPFA

SPFA是對Bellman-Ford算法的一個優(yōu)化
注意松弛操作：dis[y] = min(dis[y], dis[x] + w[i]) 什么時候這個操作才是有效的？只有當(dāng)dis[x]變小，dis[y]才可能變小當(dāng)dis[x]不變時，dis[y]`一定不會變換，所以Bellman-Ford中，大部分的更新多余且無效

如何使得每次的更新都是有效的呢？
運(yùn)用廣搜的思想，將每次更新（有效松弛）的點(diǎn)進(jìn)入隊(duì)列
初始時，將源點(diǎn)入隊(duì)，表示源點(diǎn)的最短路被更新
每次取出隊(duì)頭的點(diǎn)，對連接該點(diǎn)的所有邊進(jìn)行松弛操作。通過鄰接表將與該點(diǎn)鄰接的點(diǎn)入隊(duì)，因?yàn)檫@些點(diǎn)的dis距離被更新了
直到隊(duì)列為空，此時整張圖更新完成

注意，為防止一個點(diǎn)的重復(fù)地進(jìn)入隊(duì)列，要維護(hù)每個點(diǎn)的狀態(tài)：某個點(diǎn)入隊(duì)之前，先判斷該點(diǎn)是否已經(jīng)在隊(duì)列中

模板：

// N為點(diǎn)數(shù)，M為邊數(shù)
int dis[N];
int h[N], e[M], ne[M], w[M], idx = 1;
int q[N], hh, tt = -1;
bool st[N];

void add(int x, int y, int d)
{
	e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void spfa()
{
	memset(dis, 0x3f, sizeof(dis));
	q[++ tt] = 1, st[1] = true, dis[1] = 0; // 假設(shè)1號點(diǎn)為源點(diǎn)
	while (tt >= hh)
	{
		int x = q[hh ++ ];
		st[x] = false;
		for (int i = h[x]; i != -1; i = ne[i] )
		{
			int y = e[i];
			if (dis[x] + w[i] < dis[y]) 
			{
				dis[y] = dis[x] + w[i];
				if (!st[y]) st[y] = true, q[++ tt ] = y;
			}
		}
	}
}

出題者可能故意卡SPFA的時間，使時間復(fù)雜度達(dá)到最壞的情況O(nm)
此時只能使用其他算法

SPFA求負(fù)環(huán)

和Bellman-Ford一樣，SPFA也是運(yùn)用抽屜原理判斷圖中是否有負(fù)環(huán)

在SPFA求負(fù)環(huán)的算法中，雖然求解過程與原SPFA差不多，但是有些思想是完全不一樣的
比如dis數(shù)組不再表示其他點(diǎn)到源點(diǎn)的距離，可以認(rèn)為該數(shù)組沒有任何含義
初始化時，將dis數(shù)組的每個值置為0，甚至任意數(shù)都是可以的，只要保證每個位置的值一樣
由于現(xiàn)在要判斷圖中是否存在負(fù)環(huán)，若從一個點(diǎn)出發(fā)找負(fù)環(huán)，在非連通圖中可能無法實(shí)現(xiàn)，所以不能用單源點(diǎn)判斷負(fù)環(huán)。所以初始化時，將所有的點(diǎn)入隊(duì)，表示每個點(diǎn)都是源點(diǎn)，此時就算是非連通圖也能找到負(fù)環(huán)
dis[x] + w[i] < dis[y]：什么時候會執(zhí)行該操作？當(dāng)dis所有值都相同時，只有w[i]為負(fù)數(shù)（存在負(fù)權(quán)邊）時，該操作才會執(zhí)行。此時維護(hù)cnt數(shù)組，cnt[y] = cnt[x] + 1表示遍歷了某條存在負(fù)權(quán)邊的路徑中的一條邊，當(dāng)cnt數(shù)組中的某個值大于等于n，即cnt[i] >= n時，根據(jù)抽屜原理，該圖中存在負(fù)環(huán)

所以，求解負(fù)環(huán)時，SPFA不再是單源求解過程，而是多源求解過程。求解的問題也不再是最短路，而是負(fù)環(huán)的判斷
此時，dis數(shù)組的含義發(fā)生變化，同時引入cnt數(shù)組，存儲遍歷某條存在負(fù)權(quán)邊的路徑的邊的次數(shù)

非連通圖中的負(fù)環(huán)，邊數(shù)不可能大于等于n吧。那么根據(jù)cnt[i] >= n判斷圖中是否存在負(fù)環(huán)有問題嗎？cnt數(shù)組存儲在某條存在負(fù)權(quán)邊的路徑中遍歷的次數(shù)，當(dāng)一個負(fù)環(huán)的邊數(shù)小于n，那么我們將一直遍歷這個負(fù)環(huán)，直到cnt[i] >= n停止
最壞的情況時，所有的點(diǎn)共同構(gòu)成了負(fù)環(huán)，負(fù)環(huán)中點(diǎn)的數(shù)量與邊的數(shù)量都等于n，此時我們將遍歷圖中所有點(diǎn)一次，接著cnt[i] == n，遍歷結(jié)束，說明圖中存在負(fù)環(huán)

模板：

int h[N], e[M], ne[M], w[M], idx = 1;
int q[N], hh, tt = -1;
int dis[N], cnt[n];
bool st[N];

void add(int x, int y, int d)
{
	e[idx] = y, ne[idx] == h[x], w[idx] = d, h[x] = idx ++ ;
}

bool spfa()
{
	for (int i = 1; i <= n; ++ i )
		q[++ tt] = i, st[i] = true;

	while (tt >= hh)
	{
		int x = q[hh ++];
		st[x] = false;
		for (int i = h[x]; i != -1; i = ne[i])
		{
			int y = e[i];
			if (dis[x] + w[i] < dis[y])
			{
				dis[y] = dis[x] + w[i];
				cnt[y] = cnt[x] + 1;
				if (cnt[y] >= n) return true;
				if (!st[y]) st[y] = true, q[++ tt] = y;
			}
		}
	}
	return false;
}

多源匯最短路

Floyd

任意起點(diǎn)與終點(diǎn)的最短路問題
Floyd的時間復(fù)雜度為： O( $n^3$ )

d[k][i][j]：從i號點(diǎn)出發(fā)，只經(jīng)過1~k號這些中間點(diǎn)，到達(dá)j號點(diǎn)的最短距離
狀態(tài)更新：d[k][i][j] = d[k - 1][i][k] + d[k - 1][k][j]，觀察表達(dá)式，發(fā)現(xiàn)第一個維度可以壓縮，即d[i][j] = d[i][k] + d[k][j]

過程很簡單，三重循環(huán)進(jìn)行動態(tài)規(guī)劃
模板：

void Floyd()
{
	for (int k = 1; k <= n; ++ k )
		for (int i = 1; i <= n; ++ i )
			for (int j = 1; j <= n; ++ j )
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

注意d數(shù)組要初始化：初始化的值與鄰接矩陣一樣，由于要求解的問題是多源匯最短路，所以要初始化源點(diǎn)到源點(diǎn)的距離為0

最短路練習(xí)題

849. Dijkstra求最短路 I

849. Dijkstra求最短路 I - AcWing題庫
對圖中節(jié)點(diǎn)進(jìn)行編號，題目要求1號點(diǎn)到n號點(diǎn)的最短距離
以1號點(diǎn)作為源點(diǎn)，用樸素Dijkstra更新dis數(shù)組，獲取單源最短路

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

const int N = 510, M = 1e5 + 10;
int dis[N], g[N][N];
bool vt[N];
int n, m;

void dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    
    for (int i = 0; i < n; ++ i )
    {
        int x = -1;
        for (int j = 1; j <= n; ++ j)
            if (!vt[j] && (x == -1 || dis[j] < dis[x])) 
                x = j;

        vt[x] = true; // 從不屬于s的點(diǎn)中選擇距離源點(diǎn)最近的點(diǎn)
        for (int y = 1; y <= n; ++ y) // 用新加入的點(diǎn)更新其他點(diǎn)
            dis[y] = min(dis[y], dis[x] + g[x][y]);
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));
    
    scanf("%d%d", &n, &m);
    int x, y, d;
    while (m -- )
    {
        scanf("%d%d%d", &x, &y, &d);
        g[x][y] = min(g[x][y], d);
    }
    
    dijkstra();
    
    if (dis[n] == 0x3f3f3f3f) printf("-1\n");
    else printf("%d\n", dis[n]);
    
    return 0;
}

850. Dijkstra求最短路 II

850. Dijkstra求最短路 II - AcWing題庫
第三章搜索與圖論（二）——最短路問題,AcWing算法課課程記錄,圖論

題目給定的圖為稀疏圖，使用鄰接表存儲
和第一題一樣，要求1號點(diǎn)到n號點(diǎn)的最短距離，以1號點(diǎn)為源點(diǎn)，用Dijkstra求得單源最短路

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

typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> q;
const int N = 2e5 + 10;
int h[N], e[N], ne[N], w[N], idx = 1;
int dis[N];
bool vt[N];
int n, m;

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    q.push({ 0, 1 }), dis[1] = 0;
    
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        
        int x = t.second, d = t.first;
        if (vt[x]) continue;
        vt[x] = true;
        
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (!vt[y] && d + w[i] < dis[y])
            {
                dis[y] = d + w[i];
                q.push({ dis[y], y });
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y, d;
    while (m -- )
    {
        scanf("%d%d%d", &x, &y, &d);
        add(x, y, d);
    }
    
    dijkstra();
    if (dis[n] == 0x3f3f3f3f) printf("-1\n");
    else printf("%d\n", dis[n]);
    
    return 0;
}

debug：優(yōu)先隊(duì)列需要建小堆，默認(rèn)是建立大堆，這個真的沒有注意到
queue<PII, vector<PII>, greater<PII>>：傳greater建立小堆

853. 有邊數(shù)限制的最短路

853. 有邊數(shù)限制的最短路 - AcWing題庫
第三章搜索與圖論（二）——最短路問題,AcWing算法課課程記錄,圖論

求解具有負(fù)權(quán)邊的最短路問題一般使用SPFA，因?yàn)槠鋾r間復(fù)雜度較低。但有些最短路問題只能用Bellman-Ford求解，因?yàn)檫@類題有邊數(shù)的限制
限制的邊數(shù)就是外循環(huán)的次數(shù)，內(nèi)循環(huán)還是要對所有邊進(jìn)行松弛操作
由于圖中可能存在負(fù)權(quán)邊，當(dāng)源點(diǎn)無法遞達(dá)某一個點(diǎn)時，該點(diǎn)的dis距離可能不是最大值，而是小于最大值的較大值
假設(shè)源點(diǎn)無法到達(dá)目標(biāo)點(diǎn)y點(diǎn)，但x點(diǎn)能到達(dá)y點(diǎn)，此時源點(diǎn)也無法遞達(dá)x點(diǎn)，即dis[x] = +∞。而連接x與y的邊權(quán)為負(fù)數(shù)，那么目標(biāo)點(diǎn)y的dis距離將被更新：dis[y] = dis[x] + w，其中的dis[x]為正無窮，w為負(fù)數(shù)，那么dis[y]將被更新成一個小于正無窮的較大數(shù)
所以判斷源點(diǎn)是否能遞達(dá)其他點(diǎn)時，不能判斷dis[i] == 0x3f3f3f3f，而應(yīng)該判斷dis[i] > 0x3f3f3f3f / 2

以下代碼存在問題，無法AC

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

const int N = 510, M = 10010;
int dis[N], bup[N];
int n, m, k;

struct Edge
{
    int x, y ,w;
}edges[M];

int Bellman_Ford()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    for (int i = 0; i < k; ++ i )
    {
        memcpy(bup, dis, sizeof(dis));
        for (int j = 0; j < m; ++ j )
        {
            auto e = edges[j];
            dis[e.y] = min(dis[e.y], bup[e.x] + e.w);
        }
    }
    
    if (dis[n] > 0x3f3f3f3f / 2) return -1;
    return dis[n];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    int x, y, w;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d%d", &x, &y, &w);
        edges[i] = { x, y, w };
    }
    
    int t = Bellman_Ford();
    if (t == -1) puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

debug：某些最短路可能是負(fù)值，當(dāng)最短路為-1時，Bellman_Ford()返回的t也是-1，此時-1不能作為區(qū)分是否存在最短路的值
所以應(yīng)該直接在main函數(shù)中判斷dis[n]與0x3f3f3f3f的關(guān)系

以下是ac代碼

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

const int N = 510, M = 10010;

struct Edge
{
    int x, y, w;
}edges[M];

int dis[N], bup[N];
int n, m, k;

void bellman_ford()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    for (int i = 0; i < k; ++ i )
    {
        memcpy(bup, dis, sizeof(dis));
        for (int j = 0; j < m; ++ j )
        {
            auto t = edges[j];
            dis[t.y] = min(dis[t.y], bup[t.x] + t.w);
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    int x, y, d;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d%d", &x, &y, &d);
        edges[i] = { x, y, d };
    }
    
    bellman_ford();
    if (dis[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dis[n]);
    
    return 0;
}

851. spfa求最短路

851. spfa求最短路 - AcWing題庫
第三章搜索與圖論（二）——最短路問題,AcWing算法課課程記錄,圖論

debug：以下spfa是錯誤的，錯在松弛操作的判斷條件，當(dāng)滿足dis[x] + w[i] < dis[y]時，就要更新dis[y] = dis[x] + w[i]。然后再判斷y是否在隊(duì)列中，不能將y是否在隊(duì)列作為松弛操作的判斷條件

void spfa()
{
    memset(dis, 0x3f, sizeof(dis));
    q[++ tt] = 1, dis[1] = 0, st[1] = true;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        st[x] = false;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (!st[y] && dis[x] + w[i] < dis[y])
                st[y] = true, dis[y] = dis[x] + w[i], q[++ tt] = y;
        }
    }
}

以下是ac代碼：

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

const int N = 1e5 + 10;

int h[N], e[N], ne[N], w[N], idx = 1;
int q[N], hh, tt = -1;
int dis[N];
bool st[N]; // 某個點(diǎn)是否在隊(duì)列中
int n, m;


void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void spfa()
{
	memset(dis, 0x3f, sizeof(dis));
	q[++ tt] = 1, st[1] = true, dis[1] = 0; // 假設(shè)1號點(diǎn)為源點(diǎn)
	while (tt >= hh)
	{
		int x = q[hh ++ ];
		st[x] = false;
		for (int i = h[x]; i != -1; i = ne[i] )
		{
			int y = e[i];
			if (dis[x] + w[i] < dis[y]) 
			{
				dis[y] = dis[x] + w[i];
				if (!st[y]) st[y] = true, q[++ tt ] = y;
			}
		}
	}
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y, d;
    while (m -- )
    {
        scanf("%d%d%d", &x, &y, &d);
        add(x, y, d);
    }
    
    spfa();
    
    if (dis[n] == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", dis[n]);
    return 0;
}

852. spfa判斷負(fù)環(huán)

852. spfa判斷負(fù)環(huán) - AcWing題庫
第三章搜索與圖論（二）——最短路問題,AcWing算法課課程記錄,圖論

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

const int N = 2010, M = 10010;
int h[N], e[M], ne[M], w[M], idx = 1;
int q[M], hh, tt = -1;
int dis[N], cnt[N];
bool st[N];
int n, m;

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

bool spfa()
{
    for (int i = 1; i <= n; ++ i )
        q[++ tt] = i, st[i] = true;
    
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        st[x] = false;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (dis[x] + w[i] < dis[y])
            {
                dis[y] = dis[x] + w[i];
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n) return true;
                if (!st[y]) q[++ tt] = y, st[y] = true;
            }
        }
    }
    return false; 
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y, d;
    while (m -- )
    {
        scanf("%d%d%d", &x, &y, &d);
        add(x, y, d);
    }
    
    if (spfa()) puts("Yes");
    else puts("No");
    
    return 0;
}

debug：用原生數(shù)組模擬隊(duì)列時，隊(duì)列的長度要設(shè)置為M，之前設(shè)置為int q[N]，導(dǎo)致了TLE，排查了很久的邏輯錯誤，結(jié)果是這里錯了。看來這種邊界問題需要提前想好啊，懶得想就用STL的，但是時間差距嘛，看下圖
第三章搜索與圖論（二）——最短路問題,AcWing算法課課程記錄,圖論

854. Floyd求最短路

854. Floyd求最短路 - AcWing題庫
第三章搜索與圖論（二）——最短路問題,AcWing算法課課程記錄,圖論文章來源地址http://www.zghlxwxcb.cn/news/detail-533917.html

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

const int N = 210, M = 20010;
int n, m, k;
int d[N][N];

void flody()
{
    for (int k = 1; k <= n; ++ k )
        for (int i = 1; i <= n; ++ i )
            for (int j = 1; j <= n; ++ j )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    memset(d, 0x3f, sizeof(d));
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++ i ) d[i][i] = 0;
    
    int x, y, w;
    while (m -- )
    {
        scanf("%d%d%d", &x, &y, &w);
        d[x][y] = min(d[x][y], w);
    }
    
    flody();
    
    while (k -- )
    {
        scanf("%d%d", &x, &y);
        int t = d[x][y];
        if (t > 0x3f3f3f3f / 2) puts("impossible");
        else printf("%d\n", t);
    }
    return 0;
}

到了這里，關(guān)于第三章搜索與圖論（二）——最短路問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

第三章圖論 No.2單源最短路之虛擬源點(diǎn)，狀壓最短路與最短路次短路條數(shù)
dp是特殊的最短路，是無環(huán)圖（拓?fù)鋱D）上的最短路問題 1137. 選擇最佳線路 1137. 選擇最佳線路 - AcWing題庫對于每組測試數(shù)據(jù)，該重置的數(shù)據(jù)要重置，我沒有重置idx，導(dǎo)致TLE 處理反向建圖，還有一種擴(kuò)展做法：虛擬源點(diǎn) 設(shè)置虛擬源點(diǎn)，與每個起點(diǎn)之間連接邊權(quán)為0的邊原問題
2024年02月14日
瀏覽(26)
第三章圖論 No.3 flody之多源匯最短路，傳遞閉包，最小環(huán)與倍增
flody的四個應(yīng)用：多源匯最短路傳遞閉包找最小環(huán) 恰好經(jīng)過k條邊的最短路倍增多源匯最短路：1125. 牛的旅行 1125. 牛的旅行 - AcWing題庫直徑概念：同一連通塊中，兩個距離最遠(yuǎn)的點(diǎn)之間的距離如何求直徑？由于圖中存在著兩個連通塊，所以直接對全圖做一個flody，就能更
2024年02月14日
瀏覽(27)
搜索與圖論第六期最短路問題
Dijkstra算法?zhǔn)且环N著名的圖算法，主要用于求解有權(quán)圖中的單源最短路徑問題。它由荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾·戴克斯特拉（Edsger Wybe Dijkstra）在1956年首次提出。Dijkstra算法的核心思想是通過以下步驟逐步構(gòu)建最短路徑樹：初始化：創(chuàng)建一個空白的最短路徑字典，其中每
2024年02月20日
瀏覽(20)
搜索與圖論（acwing算法基礎(chǔ)）
排列數(shù)字 n皇后走迷宮單鏈表點(diǎn)擊跳轉(zhuǎn)至例題 idx存的是指針樹與圖的深度優(yōu)先搜索樹的重心每個節(jié)點(diǎn)都是一個單鏈表模擬隊(duì)列 hh = 0 , tt = -1 有向圖的拓?fù)湫蛄?都是從前指向后,即有向無環(huán)圖（不能有環(huán)）所有入度為0的點(diǎn)，都能排在前面的位置刪掉t-j的邊，僅僅是j的入度
2024年02月08日
瀏覽(23)
第3章：搜索與圖論【AcWing】
閱讀前導(dǎo) 本文默認(rèn)讀者有數(shù)據(jù)結(jié)構(gòu)和圖論基礎(chǔ)，本文是對圖論的幾個代表性算法的入門，雖然題目的解法比較樸素，但是比較好理解。首先簡單復(fù)習(xí)一下離散數(shù)學(xué)中圖論的相關(guān)概念。圖是由頂點(diǎn)和邊組成，頂點(diǎn)一般表示對象，邊一般表示對象之間的關(guān)系。在圖論中，多個頂
2024年02月03日
瀏覽(16)
Acwing-基礎(chǔ)算法課筆記之搜索與圖論
bellman-ford算法適用于負(fù)權(quán)邊的圖，求 1 到 n 的最多經(jīng)過k條邊的最短距離。如圖所示： 1 2 3 dist 0 ∞ infty ∞ ∞ infty ∞ ? Downarrow ? 1 2 3 dist 0 1 ∞ infty ∞ ? Downarrow ? 1 2 3 dist 0 1 2 此過程中出現(xiàn)了串聯(lián)的結(jié)果，所以是錯誤的，此時需要進(jìn)行備份操作。備份操作如下：為了
2024年01月20日
瀏覽(28)
acwing算法基礎(chǔ)課(第三講搜索與圖論)
void dfs(int u){ if(n == u){ for(int i = 0;i n;i++) puts(g[i]); puts(“”); return; } for(int i = 0;i n;i++){ if(!col[i] !dg[u+i] !udg[n - u + i]){ g[u][i] = ‘Q’; col[i] = dg[u+i] = udg[n - u + i] = true; dfs(u+1); col[i] = dg[u+i] = udg[n - u + i] = false; g[u][i] = ‘.’; } } } int main(){ scanf(“%d”,n); for(int i = 0;i n;i++){ for(int j = 0;j
2024年04月10日
瀏覽(25)
acwing算法基礎(chǔ)之搜索與圖論--kruskal算法
kruskal算法的關(guān)鍵步驟為：將所有邊按照權(quán)重從小到大排序。定義集合S，表示生成樹。枚舉每條邊(a,b,c)，起點(diǎn)a，終點(diǎn)b，邊長c。如果結(jié)點(diǎn)a和結(jié)點(diǎn)b不連通（用并查集來維護(hù)），則將這條邊加入到集合S中。 kruskal算法的時間復(fù)雜度為O(mlogm)，它用來解決稀疏圖的最小生成樹問題
2024年02月05日
瀏覽(25)
? ★ 算法基礎(chǔ)筆記（Acwing）（三）—— 搜索與圖論（17道題）【java版本】
1. 排列數(shù)字(3分鐘) 每次遍歷dfs參數(shù)是遍歷的坑位原題鏈接 2. n-皇后問題原題鏈接方法 1. 按行遍歷（過程中有回溯、剪枝）思想：每次遞歸中，遍歷一行的元素，如果可以放皇后，就遞歸到下一行，下一行中不行了，就返回來，回溯，方法2. 按每個元素遍歷（沒有減枝）
2024年02月05日
瀏覽(22)
第三章圖論 No.13拓?fù)渑判?/a>
拓?fù)湫蚝虳AG有向無環(huán)圖聯(lián)系在一起，通常用于最短/長路的線性求解裸題：1191. 家譜樹 1191. 家譜樹 - AcWing題庫差分約束+拓?fù)渑判颍?192. 獎金 1192. 獎金 - AcWing題庫由于圖中所有邊權(quán)都是正數(shù)，可以直接使用topsort求解差分約束問題根據(jù)題意，要求一個最小值，使用最長路求解
2024年02月12日
瀏覽(17)

<source id="bxjpw"></source><noscript id="bxjpw"><pre id="bxjpw"></pre></noscript>

<u id="bxjpw"></u>