目錄
一.單源最短路
1.dijkstra算法及實(shí)現(xiàn)
2.spfa算法及實(shí)現(xiàn)
（1）spafa負(fù)環(huán)判斷及實(shí)現(xiàn)
二.多源最短路
1.floyd算法及實(shí)現(xiàn)
一.單源最短路
1.dijkstra算法及實(shí)現(xiàn)
求源點(diǎn)到圖中其余各頂點(diǎn)的最短路徑
dfs效率慢,解決規(guī)模小，bfs只能邊權(quán)為1的圖
Dijkstra算法——迪杰斯塔拉算法（非負(fù)全圖）
?基本思想:
?首先假定源點(diǎn)為u，頂點(diǎn)集合V被劃分為兩部分：集合 S 和 V-S.
?初始時(shí)S中僅含有源點(diǎn)u，其中S中的頂點(diǎn)到源點(diǎn)的最短路徑已經(jīng)確定。
集合S 和V - S中所包含的頂點(diǎn)到源點(diǎn)的最短路徑的長(zhǎng)度待定，
?稱從源點(diǎn)出發(fā)只經(jīng)過S中的點(diǎn)到達(dá)V - S中的點(diǎn)的路徑為特殊路徑，
并用dist[]記錄當(dāng)前每個(gè)頂點(diǎn)對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。
實(shí)現(xiàn)從1到n的最短路徑
?輸入：
3 3
1 2 5
2 3 5
3 1 2
輸出：
2
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1001;
const int M = 10001;
int head[N];
int size1;
int n, m;
struct edge {
int v, w, next;
edge() {};
edge(int _v, int _w, int _next) {
v = _v;
w = _w;
next = _next;
}
}e[M*2];
void init() {
memset(head, -1, sizeof(head));
size1 = 0;;
}
void insert(int u,int v,int w) {
e[size1] = edge(v, w, head[u]);
head[u] = size1++;
}
void insert2(int u, int v, int w) {
insert(u, v, w);
insert(v, u, w);
}
int dis[N];
bool vis[N];
void dijkstra(int u)
{
memset(vis, false, sizeof(vis));
memset(dis, 0x3f, sizeof(dis)); //0x3f用以表示正無(wú)窮
dis[u] = 0;
int mind = 1000000000;
for (int i = 0; i < n; i++) {
int minj = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && dis[j] < mind) {
minj = j;
mind = dis[j];
}
}
if (minj == -1)
return;
vis[minj] = true;
for (int j = head[minj];~j ; j = e[j].next) { ///~j等價(jià)于j!=-1;
int v = e[j].v;
int w = e[j].w;
if (!vis[v] && dis[v] > dis[minj] + w)
dis[v] = dis[minj] + w;
}
}
}
int main()
{
init();
int u, v, w;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
insert2(u, v, w);
}
dijkstra(1);
cout << dis[n] << endl;
return 0;
}
2.SPFA算法——Shortest Path Faster Algorithm?
思路：
用數(shù)組dis記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，用鄰接表或鄰接矩陣來存儲(chǔ)圖G。
我們采取的方法是動(dòng)態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來保存待優(yōu)化的結(jié)點(diǎn)，
優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，
并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)離開u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，
如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。
這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來進(jìn)行松弛操作，直至隊(duì)列空為止
優(yōu)點(diǎn)：
（可以解決帶負(fù)權(quán)的有向圖并且在稀疏圖優(yōu)于dijsktra）
反例：
?1.出題特殊數(shù)據(jù)使SPFA算法慢，2.有負(fù)環(huán)不能解決
推薦后續(xù)優(yōu)化的dijkstra算法
實(shí)現(xiàn)：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1001;
const int M = 10001;
int head[N];
int size1;
int n, m;
struct edge {
int v, w, next;
edge() {};
edge(int _v, int _w, int _next) {
v = _v;
w = _w;
next = _next;
}
}e[M*2];
void init() {
memset(head, -1, sizeof(head));
size1 = 0;;
}
void insert(int u,int v,int w) {
e[size1] = edge(v, w, head[u]);
head[u] = size1++;
}
void insert2(int u, int v, int w) {
insert(u, v, w);
insert(v, u, w);
}
int dis[N];
bool vis[N];
void spfa(int u) {
memset(vis, false, sizeof(vis));
vis[u] = true;
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
queue<int>q;
q.push(u);
while (!q.empty()) {
u = q.front();
q.pop();
vis[u] = false;
for (int j = head[u]; ~j; j = e[j].next) {
int v = e[j].v;
int w = e[j].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}
}
int main()
{
init();
int u, v, w;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
insert2(u, v, w);
}
spfa(1);
cout << dis[n] << endl;
return 0;
}
（1）spfa判斷負(fù)環(huán)
在進(jìn)行spfa用一個(gè)數(shù)組cnt標(biāo)記每個(gè)頂點(diǎn)的入隊(duì)次數(shù)，如果一個(gè)頂點(diǎn)的入隊(duì)次數(shù)大于頂點(diǎn)總數(shù)
則表示該圖含有負(fù)環(huán)
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1001;
const int M = 10001;
int head[N];
int size1;
int n, m;
struct edge {
int v, w, next;
edge() {};
edge(int _v, int _w, int _next) {
v = _v;
w = _w;
next = _next;
}
}e[M*2];
void init() {
memset(head, -1, sizeof(head));
size1 = 0;;
}
void insert(int u,int v,int w) {
e[size1] = edge(v, w, head[u]);
head[u] = size1++;
}
void insert2(int u, int v, int w) {
insert(u, v, w);
insert(v, u, w);
}
int dis[N], in[N];
bool vis[N];
bool spfa(int u) {
memset(vis, false, sizeof(vis));
vis[u] = true;
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
memset(in, 0, sizeof(in));
in[u] = u;
queue<int>q;
q.push(u);
while (!q.empty()) {
u = q.front();
q.pop();
vis[u] = false;
for (int j = head[u]; ~j; j = e[j].next) {
int v = e[j].v;
int w = e[j].w;
if (dis[v] > dis[u] + w)
dis[v] = dis[u] + w;
if (!vis[v]) {
q.push(v);
vis[v] = false;
++in[v];
if (in[v] > n)
return true;
}
}
}
return false;
}
int main()
{
init();
int u, v, w;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
insert2(u, v, w);
}
if (spfa(1))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
二.多源最短路
1.floyd算法——（Floyd-Warshall algorithm），中文亦稱弗洛伊德算法
利用動(dòng)態(tài)規(guī)劃的思想解決帶權(quán)圖中任意兩個(gè)點(diǎn)之間最短路徑算法
優(yōu)勢(shì)：代碼簡(jiǎn)短，高效，可以解決帶負(fù)權(quán)文章來源：http://www.zghlxwxcb.cn/news/detail-619878.html
反例：不能解決帶負(fù)環(huán)
思路：
dp[0][i][j]=圖
dp[k][i][j]=從i到j(luò)可能經(jīng)過1...k最短路徑，
min(dp[k][i][j],dp[k-1][i][k]+dp[k-1][k][j])
優(yōu)化為二維：
min(dp[i][j],dp[i][k]+dp[k][j])
實(shí)現(xiàn)：
?文章來源地址http://www.zghlxwxcb.cn/news/detail-619878.html
#include<iostream>
#include<cstring>
using namespace std;
const int N = 101;
int g[N][N];
void floyd(int n) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = min(g[i][j], g[i][k] + g[j][k]);
}
}
}
}
int main()
{
memset(g, 0x3f, sizeof(g));
for (int i = 0; i < N; i++) {
g[i][i] = 0;
}
int n, m;
int u, v, w;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
g[u][v] = g[v][u] = w;
}
floyd(n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << g[i][j] << ' ';
}
cout << endl;
}
return 0;
}到了這里，關(guān)于求最短路徑的三種算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
