終于是學(xué)完了，這個(gè)最短路我學(xué)了好幾天，當(dāng)然也學(xué)了別的算法啦，也是非常的累啊。
話不多說下面看看最短路問題吧。
最短路問題是有向圖，要求的是圖中一個(gè)點(diǎn)到起點(diǎn)的距離，其中我們要輸入點(diǎn)和點(diǎn)之間的距離，來求最短路。
下面分為幾類題目：
單源匯最短路-->一個(gè)起點(diǎn)
1.邊權(quán)為正數(shù)（dijkstra）
dijkstra算法的原理其實(shí)是拿第一個(gè)點(diǎn)與相連接的點(diǎn)進(jìn)行距離上的比較，讓距離最近的點(diǎn)作為下一個(gè)比較的第一個(gè)點(diǎn)，由于是邊權(quán)為正數(shù)，所以不用去考慮負(fù)數(shù)和負(fù)環(huán)路。但是為啥我要分為兩種類型，不是因?yàn)閮?yōu)化就是比樸素好，因?yàn)樗麄兊拇鎯?chǔ)數(shù)據(jù)不同，要存儲(chǔ)的方式也是不同的，所以方法也是不同的。
方法：
dis[1]=0,dis[i]=0x3f正無窮
for(int i=1~n) 當(dāng)前已經(jīng)確定最短距離的點(diǎn)（當(dāng)然用鄰接表存儲(chǔ)的for(int i=h[st];i!=-1;i=ne[i])）
t<-不在s中的距離最近的點(diǎn)
s<-t
用t更新其他點(diǎn)的距離
(1)樸素 O(n^2) n點(diǎn)數(shù)m邊數(shù)-->邊數(shù)較多-->稠密圖-->鄰接矩陣
看題：
給定一個(gè)?n?個(gè)點(diǎn)?m?條邊的有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)均為正值。
請(qǐng)你求出?1?號(hào)點(diǎn)到?n?號(hào)點(diǎn)的最短距離，如果無法從?1?號(hào)點(diǎn)走到?n?號(hào)點(diǎn)，則輸出??1。
輸入格式
第一行包含整數(shù)?n?和?m。
接下來?m?行每行包含三個(gè)整數(shù) x,y,z，表示存在一條從點(diǎn)?x?到點(diǎn)?y?的有向邊，邊長為?z。
輸出格式
輸出一個(gè)整數(shù)，表示?1?號(hào)點(diǎn)到?n?號(hào)點(diǎn)的最短距離。
如果路徑不存在，則輸出??1。
數(shù)據(jù)范圍
1≤n≤500,
1≤m≤10^5,
圖中涉及邊長均不超過10000。
看這個(gè)
輸入樣例：
3 3
1 2 2
2 3 1
1 3 4
輸出樣例：
3代碼實(shí)現(xiàn)：
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dis[N];
bool st[N];
int Dijkstra(){
memset(dis,0x3f,sizeof dis);
dis[1]=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++)//j-x當(dāng)前的點(diǎn)
if(!st[j]&&(t==-1||dis[t]>dis[j]))
t=j;
// if(t==n)break;
st[t]=true;
for(int j=1;j<=n;j++)
dis[j]=min(dis[j],dis[t]+g[t][j]);
}
if(dis[n]==0x3f3f3f3f)return -1;
return dis[n];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
memset(g,0x3f,sizeof g);
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
cout<<Dijkstra()<<endl;
}(2)堆優(yōu)化版 O(mlogn)-->邊少-->稀疏圖-->鄰接表
給定一個(gè)?n?個(gè)點(diǎn)?m?條邊的有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)均為非負(fù)值。
請(qǐng)你求出?1?號(hào)點(diǎn)到?n?號(hào)點(diǎn)的最短距離，如果無法從?1?號(hào)點(diǎn)走到?n?號(hào)點(diǎn)，則輸出??1。
輸入格式
第一行包含整數(shù)?n?和?m。
接下來?m?行每行包含三個(gè)整數(shù) x,y,z，表示存在一條從點(diǎn)?x?到點(diǎn)?y?的有向邊，邊長為?z。
輸出格式
輸出一個(gè)整數(shù)，表示?1?號(hào)點(diǎn)到?n?號(hào)點(diǎn)的最短距離。
如果路徑不存在，則輸出??1。
數(shù)據(jù)范圍
1≤n,m≤1.5×10^5,
圖中涉及邊長均不小于?0，且不超過 10000。
數(shù)據(jù)保證：如果最短路存在，則最短路的長度不超過?10^9。
輸入樣例：
3 3
1 2 2
2 3 1
1 3 4
輸出樣例：
3代碼實(shí)現(xiàn)（因?yàn)槭顷?duì)列嘛，咱們也可以使用模擬隊(duì)列）：
#include<bits/stdc++.h>
#include<cstring>//memset函數(shù)的頭文件
#include<iostream>
#include<algorithm>
#include<queue>
#define xx first
#define yy second
using namespace std;
const int N = 150010;
typedef pair<int, int>PII;//前者是距離 堆中按照前者距離排序 后者是點(diǎn)序號(hào)
priority_queue<PII, vector<PII>, greater<PII>>heap;//小根堆
int h[N], w[N], e[N], ne[N], idx;//稀疏圖用鄰接表儲(chǔ)存 w[N]存權(quán)重
int dist[N];//起點(diǎn)點(diǎn)到終點(diǎn)的(當(dāng)前)最短距離
bool vis[N];//標(biāo)記起點(diǎn)到某個(gè)點(diǎn)的最短距離是否確定
int st,ed;//起點(diǎn)到終點(diǎn)
int n, m;
//數(shù)組模擬鄰接表的插入函數(shù)
void add(int a, int b, int c){//存在一條從點(diǎn)a到點(diǎn)b的有向邊 距離為c
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int Dijkstra(int st, int ed){
//初始設(shè)定起點(diǎn)點(diǎn)到其他所有點(diǎn)距離為正無窮
memset(dist, 0x3f, sizeof dist);
//起點(diǎn)到起點(diǎn)距離為0 加入堆
dist[st] = 0;
//第一參數(shù)是距離
//第二參數(shù)是終點(diǎn)編號(hào)
heap.push({ 0,st });
while (heap.size()){
auto t = heap.top();
heap.pop();//取出后一定要彈出
int ver = t.yy, distance = t.xx;//ver取得該點(diǎn)的下標(biāo)
if (vis[ver])continue;//已經(jīng)確定了就跳過
//要做就先確定下來
//出隊(duì)時(shí)確定加入S集合
vis[ver] = true;
//把確定下來的那個(gè)點(diǎn)能拓展到的新點(diǎn) 加入堆
for (int i = h[ver];~i;i = ne[i]){
int j = e[i];
if (dist[j] > distance + w[i]){
dist[j] = distance + w[i];
heap.push({ dist[j],j });
}
}
}
if (dist[ed] == 0x3f3f3f3f)return -1;//不連通
return dist[ed];
}
int main(){
memset(h, -1, sizeof h);//初始化鄰接表表頭
scanf("%d%d", &n, &m);
while (m--){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d\n", Dijkstra(1, n));
}2.存在負(fù)邊權(quán)
貝爾曼的原理嘛，是一個(gè)叫做三角不等式的松弛操作實(shí)現(xiàn)的，但是由于是雙重循環(huán)把所有的邊都遍歷了一遍，所以時(shí)間復(fù)雜度為O(nm)，而相對(duì)于下面的SPFA算法嘛，一般都比較常用spfa。
(1)Bellman-ford O(nm)
你看這個(gè)可以在1->2->3->4->2走無窮次，導(dǎo)致最終結(jié)果為負(fù)無窮?
但是他可以走有限條邊，即使是萬能的spfa也不行，因?yàn)檫@就是遍歷的一步。
給定一個(gè)?n?個(gè)點(diǎn)?m?條邊的有向圖，圖中可能存在重邊和自環(huán)，?邊權(quán)可能為負(fù)數(shù)。
請(qǐng)你求出從?1?號(hào)點(diǎn)到?n?號(hào)點(diǎn)的最多經(jīng)過?k?條邊的最短距離，如果無法從?1?號(hào)點(diǎn)走到?n?號(hào)點(diǎn)，輸出?impossible。
注意：圖中可能?存在負(fù)權(quán)回路?。
輸入格式
第一行包含三個(gè)整數(shù) n,m,k。
接下來?m?行，每行包含三個(gè)整數(shù)x,y,z，表示存在一條從點(diǎn)?x?到點(diǎn)?y?的有向邊，邊長為?z。
點(diǎn)的編號(hào)為 1～n。
輸出格式
輸出一個(gè)整數(shù)，表示從?1?號(hào)點(diǎn)到?n?號(hào)點(diǎn)的最多經(jīng)過?k?條邊的最短距離。
如果不存在滿足條件的路徑，則輸出?impossible。
數(shù)據(jù)范圍
1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n，
任意邊長的絕對(duì)值不超過?10000。
輸入樣例：
3 3 1
1 2 1
2 3 1
1 3 3
輸出樣例：
3代碼實(shí)現(xiàn)：
#include<bits/stdc++.h>
#include<cstring>
#include<iomanip>
#include<iostream>
using namespace std;
const int N=510,M=1e4+10;
int n,m,k;
int dis[N],backup[N];
struct tu
{
int a,b,w;
}edge[M];
void Bellman_ford(){
memset(dis,0x3f,sizeof dis);
dis[1]=0;
for(int i=0;i<k;i++){
memcpy(backup,dis,sizeof dis);
for(int j=0;j<m;j++){
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dis[b]=min(dis[b],backup[a]+w);
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){
int a,b,w;
cin>>a>>b>>w;
// edge[i].a=a,edge[i].b=b,edge[i].w=w;
edge[i]={a,b,w};
}
Bellman_ford();
if(dis[n]>0x3f3f3f3f/2)cout<<"impossible";
else cout<<dis[n];
}(2)SPFA O(m)，最壞O(nm)-->貪心
前提是：
不含負(fù)環(huán)，但是同樣適用于dijkstra題目
這個(gè)算法雖然不能適用于求負(fù)環(huán)的最短路，但是他可以判斷是不是含有負(fù)環(huán)，詳細(xì)看注釋掉的部分。
給定一個(gè)?n?個(gè)點(diǎn)?m?條邊的有向圖，圖中可能存在重邊和自環(huán)，?邊權(quán)可能為負(fù)數(shù)。
請(qǐng)你求出?1?號(hào)點(diǎn)到?n?號(hào)點(diǎn)的最短距離，如果無法從?1?號(hào)點(diǎn)走到?n?號(hào)點(diǎn)，則輸出?impossible。
數(shù)據(jù)保證不存在負(fù)權(quán)回路。
輸入格式
第一行包含整數(shù)?n?和?m。
接下來?m 行每行包含三個(gè)整數(shù) x,y,z，表示存在一條從點(diǎn)?x?到點(diǎn)?y?的有向邊，邊長為?z。
輸出格式
輸出一個(gè)整數(shù)，表示?1?號(hào)點(diǎn)到?n?號(hào)點(diǎn)的最短距離。
如果路徑不存在，則輸出?impossible。
數(shù)據(jù)范圍
1≤n,m≤10^5,
圖中涉及邊長絕對(duì)值均不超過?10000。
輸入樣例：
3 3
1 2 5
2 3 -3
1 3 4
輸出樣例：
2?代碼實(shí)現(xiàn)：
#include<cstring>//memset函數(shù)的頭文件
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100010;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool vis[N];
int n, m;
// int cnt[N];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
vis[1]=true;
while(q.size()){
int t=q.front();
q.pop();
vis[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
// cnt[j]=cnt[t]+1;
// if(cnt[j]>=n)return true;//判斷是不是存在負(fù)環(huán)
if(!vis[j]){
q.push(j);
vis[j]=true;
}
}
}
}
return dist[n];
// return false;
}
signed main(){
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m -- ){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int t=spfa();
if(t==0x3f3f3f3f) puts("impossible");
else printf("%d",t);
// if(spfa())puts("Yes");
// else puts("No");
}多源匯最短路 Floyd O(n^3)-->dp
給定一個(gè)?n?個(gè)點(diǎn)?m?條邊的有向圖，圖中可能存在重邊和自環(huán)，邊權(quán)可能為負(fù)數(shù)。
再給定?k?個(gè)詢問，每個(gè)詢問包含兩個(gè)整數(shù)?x?和?y，表示查詢從點(diǎn)?x?到點(diǎn)?y?的最短距離，如果路徑不存在，則輸出?impossible。
數(shù)據(jù)保證圖中不存在負(fù)權(quán)回路。
輸入格式
第一行包含三個(gè)整數(shù)?n,m,k。
接下來?m?行，每行包含三個(gè)整數(shù) x,y,z，表示存在一條從點(diǎn)?x?到點(diǎn)?y?的有向邊，邊長為?z。
接下來?k?行，每行包含兩個(gè)整數(shù)?x,y，表示詢問點(diǎn)?x?到點(diǎn)?y?的最短距離。
輸出格式
共?k?行，每行輸出一個(gè)整數(shù)，表示詢問的結(jié)果，若詢問兩點(diǎn)間不存在路徑，則輸出?impossible。
數(shù)據(jù)范圍
1≤n≤200,
1≤k≤n2
1≤m≤20000,
圖中涉及邊長絕對(duì)值均不超過 10000。
輸入樣例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
輸出樣例：
impossible
1?代碼實(shí)現(xiàn)：文章來源：http://www.zghlxwxcb.cn/news/detail-811237.html
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=200+10,INF=1e9;
int m,n,Q;
int d[N][N];
void floyd(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
signed main(){
scanf("%d%d%d",&n,&m,&Q);
//init
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)d[i][j]=0;
else d[i][j]=INF;
//input
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
d[a][b]=min(d[a][b],c);
}
floyd();
while(Q--){
int a,b;
scanf("%d%d",&a,&b);
if(d[a][b]>INF/2)
puts("impossible");
else
printf("%d",d[a][b]);
}
}
以上就是求最短路的所有方法啦。文章來源地址http://www.zghlxwxcb.cn/news/detail-811237.html
到了這里，關(guān)于圖論：最短路（dijkstra算法、bellman算法、spfa算法、floyd算法）詳細(xì)版的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
