昨天： 图论-概念与记录图的方法
以上是昨天的Blog，有需要者请先阅读完以上再阅读今天的Blog。
可能今天的有点乱，好好理理，认真看完相信你会懂得
分割线
第二天
引子：昨天我们讲了讲图的概念与记录图的方法，那么大家有一定的底子了，我们就开始初步接触图论算法了！
我们只讲Dijkstra和Floyd，因为其实在比赛中会这两个算法就很好了。
今天我们要讲的是：最短路径问题
Top1：最短路的概念
相信大家都知道有一款Made in China的导航软件——百度导航。那么他们是怎么为我们导航的？就是使用了今天我们要学的问题 最短路径 。
$\color{red}\text{ 重点：最短路问题就是一个点到另一个最短的路径！ }$
最短路术语：
松弛： 既然求一个点到另一个点最短的路径，那么肯定就会有更优的路径替代目前路径的操作。这就叫做 松弛操作。
中转点： 一个点到另一个点不一定是有直接道路连接的，可能会经过一些别的点，我们就叫那些点叫做 中转点 。
Top2:Floyd算法
现在大家都知道最短路是什么了，那么从简单到复杂，我们先来看看新手必懂的算法。
Floyd简单粗暴，就是枚举三个点，一个起点，一个终点，一个中转点。看 起点到中转点的路径 加上 中转点到终点的路径 是不是小于 目前起点到终点的路径 即可（就是不断松弛）。
显而易见，Floyd算法很好懂，就是时间复杂度高了点—— $N^3$ 的复杂度。而且，Floyd是多源最短路，询问时只需调用dis就行了。
所以， 当 N 大于1000时，慎用！
代码就很简答啦(蒟蒻用邻接矩阵写的)：
//如果为无向图,dis就会对称,Floyed的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$
怎么优化呢？很简单——在寻找离黑点最近的白点时，使用优先队列即可。
优先队列Dijkstra：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 800 + 10;
const int MAX = 1e9;
int n,m,p,x,y,z;
int a[MAXN];
int dis[MAXN];
int tot[MAXN][MAXN];
vector<int> nei[MAXN];
struct Node{
int num,dist;
bool operator < (const Node& next) const {
return dist > next.dist;
}
};
void Dijkstra(int start){
priority_queue <Node> cow;
for(int i = 1;i <= n; i++){
dis[i] = 2e9;
}
dis[start] = 0;
Node tt = {start,0};
cow.push(tt);
while(!cow.empty()){
tt = cow.top();
cow.pop();
int u = tt.num;
for(int i = 0;i < nei[u].size(); i++){
int p = nei[u][i];
if(dis[u] + tot[u][p] < dis[p]){
dis[p] = dis[u] + tot[u][p];
Node next;
next.num = p;
next.dist = dis[p];
cow.push(next);
}
}
}
return;
}
int main(){
scanf("%d%d%d",&n,&m);
for(int i = 1;i <= n; i++)
for(int j = 1;j <= i; j++){
tot[i][j] = tot[j][i] = i == j ? 0 : MAX;
}
for(int i = 1;i <= m; i++){
scanf("%d%d%d",&x,&y,&z);
tot[x][y] = z;
tot[y][x] = z;
nei[x].push_back(y);
nei[y].push_back(x);
}
int s,t;
scanf("%d%d",&s,&t);
Dijkstra(s);
cout<<dis[t]<<"\n";
return 0;
}顺便带一下SPFA的算法模板和用动态数组记录的Dijkatra(这里不做详解了，有需要的人可以复制看一下)
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;
}
动态数组Dijkstra：
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int n, p, c;
const int INF = 1e9;
int cow[805], dis[805], vertex[805][805];
vector<int> neighbor[805];
struct Node
{
int id, dist;
bool operator < (const Node & second) const
{
return dist > second.dist;
}
};
void dijkstra(int start)
{
priority_queue<Node> pq;
for(int i = 1; i <= p; i++)
{
dis[i] = INF;
}
dis[start] = 0;
Node cur = {start, 0}; //起始点和其到dis[start]
pq.push(cur);
while(!pq.empty())
{
cur = pq.top();
pq.pop();
int u = cur.id;
for(int i=0; i <= neighbor[u].size() - 1; i++)
{
int v = neighbor[u][i]; //与u相邻的边v
if(dis[u] + vertex[u][v] < dis[v])
{
dis[v] = dis[u] + vertex[u][v];
Node next;
next.id = v;
next.dist = dis[v];
pq.push(next);
}
}
}
return;
}
int main()
{
cin >> n >> p >> c;
for(int i = 1; i <= n; i++) //输入每头牛所在的位置
{
cin >> cow[i];
}
for(int i=1; i <= p; i++)
{
for(int j=1; j <= p; j++)
{
vertex[i][j] = (i == j) ? 0 : INF;
}
}
for(int i=1; i <= c; i++) //输入每一条边
{
int a, b, d;
cin >> a >> b >> d;
vertex[a][b] = d;
vertex[b][a] = d;
neighbor[a].push_back(b);
neighbor[b].push_back(a);
}
int ans = INF;
for(int i=1; i <= p; i++) //注意是循环牧场
{
dijkstra(i); //假如把糖放在第i个牧场
int sum = 0;
for(int j=1; j <= n; j++)
{
sum = sum + dis[cow[j]];
}
ans = min(ans, sum);
}
cout << ans;
return 0;
}