繼續復習資料結構和演算法，總結一下求解最短路徑的一些演算法，
弗洛伊德(floyd)演算法
弗洛伊德演算法是最容易理解的最短路徑演算法，可以求圖中任意兩點間的最短距離，但時間復雜度高達\(O(n^3)\)，主要思想就是如果想縮短從一個點到另一個點的距離，就必須借助一個中間點進行中轉，比如A點到B點借助C點中轉的話AB的距離就可以更新為\(D(a,b)=Min(D(a,b),D(a,c)+D(c,b))\)，這樣我們用每一個結點作為中轉結點，嘗試對另每兩個結點進行距離更新，總共需要三層回圈進行遍歷，
核心代碼如下，圖存盤在鄰接矩陣G中，
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
G[j][k] = min(G[j][k], G[j][i] + G[i][k]);
}
}
}
迪杰斯特拉(Dijkstra)演算法
迪杰斯特拉演算法是一種求解單源最短路徑的演算法，給定一個結點，可以求出圖上各個結點到該結點最短距離，
沒學過的話推薦看看這個視頻：https://www.bilibili.com/video/av21376839?p=13，從8分鐘開始，看完之后基本上就明白了Dijkstra演算法的運行程序，總結一下就是不斷尋找離源點最近的點并將其作為新的源點去更新其他點到目標點的距離，
代碼如下，nowIndex代表當前源點編號，minDis是當前源點到其他點的最短距離，用于選擇下一個源點，dis陣列存盤每個點到最終目標點的距離，也就是結果，mark陣列用于標記結點是否被當作源點過，
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 100000000
int G[10][10];
int dis[10];
bool mark[10];
int n, m;
void dijkstra(int nowIndex)
{
mark[nowIndex] = true;
for (int i = 1; i <= n; i++)//先將跟源點直接相連的結點更新一遍
dis[i] = min(dis[i], G[nowIndex][i]);
for (int i = 1; i < n; i++)//回圈n-1次，因為源點已經更新過了
{
int minDis = inf;
for (int j = 1; j <= n; j++)//找離當前源點最近的點
{
if (!mark[j] && dis[j] < minDis)
{
minDis = dis[j];
nowIndex = j;
}
}
mark[nowIndex] = true;
for (int j = 1; j <= n; j++)//用當前源點去更新
dis[j] = min(dis[j], dis[nowIndex] + G[nowIndex][j]);
}
}
int main()
{
cin >> n >> m;//輸入頂點數和邊數
int u, v, w;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
G[i][j] = inf;
else
G[i][j] = 0;
for (int i = 1; i <= n; i++)
dis[i] = inf;
for (int i = 0; i < m; i++)
{
cin >> u >> v >> w;//輸入無向邊
G[u][v] = w;
G[v][u] = w;
}
dijkstra(1);//以1號結點為源點
for (int i = 1; i <= n; i++)
{
cout << dis[i] << ' ';
}
return 0;
}
鄰接表實作
使用鄰接表存盤圖能大大降低空間復雜度，代碼如下：
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 100000000
#define maxN 10000
int value[maxN], to[maxN], nextL[maxN];
int head[maxN], total;
int dis[maxN];
bool mark[maxN];
int n, m;
void dijkstra(int nowIndex)
{
for (int i = 0; i <= n; i++)dis[i] = inf;
dis[nowIndex] = 0;
mark[nowIndex] = true;
for (int i = head[nowIndex]; i; i = nextL[i])
{
dis[to[i]] = min(dis[to[i]], dis[nowIndex] + value[i]);
}
for (int i = 1; i < n; i++)//回圈n-1次，因為源點已經更新過了
{
int minDis = inf;
for (int j = 1; j <= n; j++)//找離當前源點最近的點
{
if (!mark[j] && dis[j] < minDis)
{
minDis = dis[j];
nowIndex = j;
}
}
mark[nowIndex] = true;
for (int j = head[nowIndex]; j; j = nextL[j])
{
dis[to[j]] = min(dis[to[j]], dis[nowIndex] + value[j]);
}
}
}
void AddLine(int a, int b, int c)
{
total++;
to[total] = b;
value[total] = c;
nextL[total] = head[a];
head[a] = total;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
AddLine(a, b, c);
}
dijkstra(1);
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
return 0;
}
堆優化
普通的Dijkstra時間復雜度為\(O(n^2)\)，但可以通過優化達到\(O(nlogn)\)，注意在上面的回圈中我們每次都要取出離當前源點最近的點，所以可以用優先級佇列來優化，每次搜索將修改過dis的點進隊，然后每次取隊首就是最近的點，
代碼如下：
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define inf 100000000
#define maxN 10010
int s;
int value[500001], to[500001], nextL[500001];
int head[maxN], total;
int dis[maxN];
bool mark[maxN];
int n, m;
typedef pair<int, int> disID;
priority_queue<disID,vector<disID>,greater<disID>> q;
void dijkstra(int nowIndex)
{
for (int i = 0; i <= n; i++)dis[i] = inf;
dis[nowIndex] = 0;
q.push(disID(0, nowIndex));
while (!q.empty())
{
int t = q.top().second;
q.pop();
if (mark[t])continue;
mark[t] = true;
for (int i = head[t]; i ; i=nextL[i])
{
if (dis[to[i]] > dis[t] + value[i])
{
dis[to[i]] = dis[t] + value[i];
q.push(disID(dis[to[i]], to[i]));
}
}
}
}
void AddLine(int a, int b, int c)
{
total++;
to[total] = b;
value[total] = c;
nextL[total] = head[a];
head[a] = total;
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
AddLine(a, b, c);
}
dijkstra(s);
for (int i = 1; i <= n; i++)
{
cout << dis[i] << ' ';
}
return 0;
}
Bellman-ford演算法
上面的Dijkstra演算法存在一個問題就是不能處理存在負權邊的情況，只要有邊的權值是負數就不能用，這時可以用Bellman-ford演算法解決，
Bellman-ford演算法的思想是這樣的，我們將每條邊的起點、權值、終點存盤為三個陣列from[i],val[i],to[i]，然后掃描每一條邊，看能不能通過走這條邊來使dis[to[i]]減少，
代碼很簡單如下：
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define inf 100000000
int from[10000], val[10000], to[10000];
int dis[10000];
int n, m;
void Bellman_ford(int u)
{
for (int i = 0; i <= n; i++)dis[i] = inf;
dis[u] = 0;
while (true)
{
bool update = false;
for (int i = 1; i <= m; i++)
{
if (dis[from[i]] != inf && dis[to[i]] > dis[from[i]] + val[i])
{
dis[to[i]] = dis[from[i]] + val[i];//更新
update = true;
}
}
if (!update)break;//直到每一條邊都不能使dis減少
}
}
int main()
{
cin >> n >> m ;
for (int i = 1; i <= m; i++)
{
cin >> from[i] >> to[i] >> val[i];
}
Bellman_ford(1);
for (int i = 1; i <= n; i++)
cout << dis[i] << ' ';
return 0;
}
演算法中的while回圈最多回圈n-1次，所以Bellman-ford的時間復雜度是\(O(mn)\)，不僅能處理負權邊，而且在稀疏圖(頂點數遠多于邊數)當中比Dijkstra快，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91940.html
標籤：其他
下一篇：什么是陣列？