2019/11/15 更新日志
發現我的Dijstra優先佇列模板有點問題，修改了，并在多處刪繁就簡，增添詳細注釋，
昨天： 圖論-概念與記錄圖的方法
以上是昨天的Blog，有需要者請先閱讀完以上再閱讀今天的Blog，
分割線
第二天
引子：昨天我們簡單講了講圖的概念與記錄圖的方法，那么大家有一定的底子了，我們就開始初步接觸圖論演算法了！
我們只講Dijkstra和Floyd，因為其實在比賽中會這兩個演算法就很好了，
今天我們要講的是：最短路徑問題
Top1：最短路的概念
相信大家都知道有一款Made in China的導航軟體——百度導航，那么他們是怎么為我們導航的？就是使用了今天我們要學的問題 最短路徑 ，
說不定你學了之后就可以做一個導航的 是不是有點小激動？
\(重點：最短路問題就是一個點到另一個最短的路徑！\)
最短路專業術語：
中轉點： 一個點到另一個點不一定是有直接道路連接的，可能會經過一些別的點，我們就叫那些點叫做 中轉點 ，
松弛： 比如現在從 \(I\) 點到 \(J\) 點的邊權為 \(X\) ，而現在有一個點 \(K\) ，\(K\) 到 \(I\) 的邊權為 \(Y\) ，\(K\) 到 \(J\) 的邊權為 \(Z\)，如果 \(Y\) + \(Z\) < \(X\) ，也就是 (\(I\) 點到 \(J\) 點的路徑邊權) 比 (\(K\) 到 \(J\) 的邊權) 加上 (\(K\) 到 \(I\) 的邊權) 還要大，那么顯而易見， \(I\) 到 \(J\) 的直接路徑 \(X\) 可以由中轉點 \(K\) 降到 \(Y + Z\)，使得 \(I\) 到 \(J\) 的最短路徑更優，
Top2:Floyd演算法
現在大家都知道最短路是什么了，那么從簡單到復雜，我們先來看看新手必懂的演算法，
Floyd簡單粗暴，就是列舉三個點，一個起點，一個終點，一個中轉點，看 起點到中轉點的路徑 加上 中轉點到終點的路徑 是不是小于 目前起點到終點的路徑 即可（就是不斷松弛），
顯而易見，Floyd演算法很好懂，就是時間復雜度高了點—— \(N^3\) 的復雜度，而且，Floyd是多源最短路，詢問時只需呼叫dis就行了，
所以， 當 N 大于1000時，慎用！
代碼就很簡答啦(蒟蒻用鄰接矩陣寫的)：
//如果為無向圖,dis就會對稱,Floyd的j就只要到i,且dis[i][j]dis[j][i] 要一起更新
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 10;
int n,m;
int x,y,z;
int dis[MAXN][MAXN];
void Floyd(){
for(int k = 1;k <= n; k++)
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n/*i*/; j++)
if(dis[i][k] + dis[k][j] < dis[i][j])dis[i][j] = dis[i][k] + dis[k][j];
return;
}
int main(){
cin>>n>>m;
for(int i = 1;i <= n; i++)dis[i][i] = 0;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++){
if(i != j)dis[i][j] = 1e9;
}
for(int i = 1;i <= m; i++){
cin>>x>>y>>z;
dis[x][y] = z;
}
Floyd();
for(int i = 1;i <= n; i++){
for(int j = 1;j <= n; j++){
cout<<dis[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
Top3：Dijkstra演算法
Dijkstra與Floyd相反，是單元最短路，即只能求出一個點到其他所有點的最短路，
Dijkstra屬于貪心的思想，正解：
首先定義兩個種類——黑點和白點，黑點就是在目前算完最短路徑的點，白點反之，
每次在白點中找一個離目前任意一個黑點最近的，加入黑點，更新白點到原點的最短路即可，
代碼如下：注意：這里的dis不再是鄰接矩陣，是單源最短路徑，tot才是鄰接矩陣！
鄰接矩陣，蒟蒻是用洛谷P1828 香甜的黃油 Sweet Butter 作為例題寫的模板，體諒一下
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
struct Node{
int x,y;
}f[MAXN];
int n,m,a,b,s,t;
bool black[MAXN];
double dis[MAXN];
double tot[MAXN][MAXN];
double calc(int i,int j){
return sqrt((f[i].x - f[j].x) * (f[i].x - f[j].x) + (f[i].y - f[j].y) * (f[i].y - f[j].y));
}
double Dijkstra(int start,int end){
for(int i = 1;i <= n; i++){
dis[i] = tot[start][i];
}
dis[start] = 0;
black[start] = true;
for(int i = 1;i < n; i++){
double M = 2e9;
int u = start;
for(int j = 1;j <= n; j++){
if(dis[j] < M && !black[j]){
M = dis[j];
u = j;
}
}
if(u == start)continue;
//此處的判斷與前面的u = start對應,若該圖存在一個單獨的點這里就要加上
//否則可以u = 0,這個判斷刪掉
black[u] = true;
for(int j = 1;j <= n; j++){
if(black[j])continue;
if(dis[u] + tot[u][j] < dis[j]){
dis[j] = dis[u] + tot[u][j];
}
}
}
return dis[end];
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++){
tot[i][j] = i == j ? 0 : 1e9;
}
for(int i = 1;i <= n; i++){
scanf("%d%d",&f[i].x,&f[i].y);
}
scanf("%d",&m);
for(int i = 1;i <= m; i++){
scanf("%d%d",&a,&b);
tot[a][b] = calc(a,b);
tot[b][a] = tot[a][b];
}
scanf("%d%d",&s,&t);
printf("%.2f",Dijkstra(s,t));
return 0;
}
所以，Dijkstra的時間復雜度是 \(N^2\)
怎么優化呢？很簡單——在尋找離黑點最近的白點時，使用優先佇列即可，
但是這里要注意的是，我們樸素的使用單調佇列維護，在洛谷 P4779 【模板】單源最短路徑 中會TLE，
為什么呢？
我們的優先佇列不想 set 等 STL ，沒有自動去重的功能，所以當佇列中有多個相同的元素時，Dijkstra的效率會大大減少，
所以 ，我們需要一個bool型的陣列，不難想到，該陣列用來記錄 每個元素當前在佇列中是否存在，
細節又來了， 我們bool型陣列的定義是 每個元素當前在佇列中是否存在， 那么我們每次在優先佇列彈出隊首進行操作時，我們需要 將隊首的bool標記取消，
一個元素可以多次單獨出現在佇列，但是不能一次多個出現在佇列，
雖然多次拓展到隊首，但是隊首到源點的最短路徑 可能 更新了，所以我們不妨再次從隊首再次進行拓展，更新周圍點的答案， 這就是我們為什么要將隊首的bool標記取消，
優先佇列Dijkstra（機房大佬說我這是SPFA，無解）：
#include<bits/stdc++.h>
#include<cctype>
#pragma GCC optimize(2)
#define in(a) a = read()
#define out(a) write(a),printf(" ")
#define outn(a) write(a),putchar('\n')
#define ll long long
#define rg register
#define New int
using namespace std;
namespace IO_Optimization{
inline New read()
{
New X = 0,w = 0;
char ch = 0;
while(!isdigit(ch))
{
w |= ch == '-';
ch=getchar();
}
while(isdigit(ch))
{
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
inline void write(New x)
{
if(x < 0) putchar('-'),x = -x;
if(x > 9) write(x/10);
putchar(x % 10 + '0');
}
#undef New
}
using namespace IO_Optimization;
const int MAXN = 1000000 + 2;
int n,m,s,x,y,z,len,p;
int dis[MAXN],nxt,val;
struct Node
{
int num,dist;
inline bool operator <(const Node &nnxt)const{
return dist > nnxt.dist;
}
};
vector<Node> nei[MAXN];
bool vis[MAXN];
inline void Dijkstra(int start)
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(vis,false,sizeof(vis));
priority_queue<Node>q;
Node cur = {start,0};
q.push(cur);
dis[start] = 0;
vis[start] = true;
while(!q.empty())
{
cur = q.top();
q.pop();
p = cur.num;
vis[p] = false;
len = nei[p].size();
for(rg int i = 0;i < len; ++i)
{
nxt = nei[p][i].num;
val = nei[p][i].dist;
if(dis[nxt] > dis[p] + val)
{
dis[nxt] = dis[p] + val;
if(!vis[nxt])
{
Node tmp = {nxt,dis[nxt]};
q.push(tmp);
vis[nxt] = true;
}
}
}
}
return;
}
int main()
{
in(n),in(m),in(s);
for(rg int i = 1;i <= m; ++i)
{
in(x),in(y),in(z);
nei[x].push_back((Node){y,z});
}
Dijkstra(s);
for(rg int i = 1;i <= n; ++i)
out(dis[i] == 0x3f3f3f3f ? 2147483647 : dis[i]);
return 0;
}
順便帶一下SPFA的演算法模板和用動態陣列記錄的Dijkstra(這里不做詳解了，有需要的人可以復制看一下)
SPFA：
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n, p, c, cow[801], a, b, d, cnt = 0, sum = 0, ans = 2147483647;
int dis[10000], w[10000], next[10000], to[10000], first[10000] = {0};
bool exist[10000] = {false};
queue<int> q;
void addEdge(int u, int v, int weight)
{
cnt++; //邊的編號
to[cnt] = v; //第cnt條邊指向點v
w[cnt] = weight; //第cnt條邊的權值
next[cnt] = first[u]; // 第cnt條邊指向連接點u的第一條邊
first[u] = cnt; //將連接點u的第一條邊更新為第cnt條邊
return;
}
void spfa(int start)
{
memset(exist, false, sizeof(exist)); //一開始所有點在佇列外
memset(dis, 0x7f, sizeof(dis)); //將所有點到起始點的距離置為極大值
dis[start] = 0;
q.push(start); //起始點入佇列
exist[start] = true;
while(!q.empty())
{
int head = q.front(); //取佇列的第一個點
q.pop();
exist[head] = false;
for(int e = first[head]; e != 0; e = next[e]) //回圈head連接的每一條邊
{
//松弛操作
if(dis[head] + w[e] < dis[to[e]])
{
dis[to[e]] = dis[head] + w[e];
if(exist[to[e]] == false)
{
q.push(to[e]); //將被更新的點入佇列
exist[to[e]] = true;
}
}
}
}
return;
}
int main()
{
cin >> n >> p >> c;
for(int i=1; i <= n; i++) //輸入每頭牛所在的位置
{
cin >> cow[i];
}
for(int e=1; e <= c; e++) //輸入每一條邊
{
cin >> a >> b >> d;
addEdge(a, b, d);
addEdge(b, a, d);
}
for(int i=1; i <= p; i++) //注意是回圈牧場
{
spfa(i);
sum = 0;
for(int j=1; j <= n; j++)
{
sum = sum + dis[cow[j]];
}
ans = min(ans, sum);
}
cout << ans;
return 0;
}
好了，第二天就到這里，是不是都聽懂了呢狗屁？歡迎在下方留言！
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/24274.html
標籤：Windows
上一篇：httprunner運行報錯問題：base url missed
下一篇：win黑視窗命令