欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

图论-最短路径

程序员文章站 2022-07-01 13:44:31
昨天: __ "图论 概念与记录图的方法" __ 以上是昨天的Blog,有需要者请先阅读完以上再阅读今天的Blog。 可能今天的有点乱,好好理理,认真看完相信你会懂得 分割线 第二天 引子:昨天我们~~简单~~讲了讲图的概念与记录图的方法,那么大家有一定的底子了,我们就开始初步接触图论算法了! 我们 ......

昨天: 图论-概念与记录图的方法

以上是昨天的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;
}

好了,第二天就到这里,是不是都听懂了呢狗屁?欢迎在下方留言!