Dijkstra狄克斯特拉-最短路径问题

news/2024/7/15 17:39:32 标签: 图论, dijkstra, 算法, 数据结构, 队列

教学视频

狄克斯特拉算法

与prim普里姆算法的不同之处

prim与dijkstra算法都是基于"蓝白点私思想" ,所谓蓝白点思想就是开局所有点皆为蓝点,之后逐个加入,每次选出白点,直到所有蓝点消失,prim与dijkstra算法实现都有一个d数组,但是d数组的含义却不相同,prim是集合V中到集合G-V中,两点之间的最小值,而dj是从源点出发,到该点的最小值,两种算法的d数组含义截然不同,但是实现逻辑都是基于蓝白点思想,先找出d数组中为最小值的结点u,在遍历与u相邻结点进行更新d数组中的值,区别在于如何更新prim是 m[u][v]<d[v]就更新,而dj是d[u]+m[u][v]<d[j]就更新!

注意:dijkstra算法不能用于权值为负的情况。会环化!

prime和dijkstra算法都是O(V^2),在没有优先队列优化的情况下。

代码实现:

#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int maxn=1000+10;
int n,ans,ecnt,m;
int head[maxn],vis[maxn];
int d[maxn],ma[maxn][maxn];
int p[maxn];
struct node
{
    int u,v,next;
} E[maxn];


void add(int u,int v)
{
    E[++ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].next=head[u];
    head[u]=ecnt;
}

void prim()
{
    int u;
    memset(d,0x7f7f7f7f,sizeof(d));
    d[1]=0;
    for(int i=1;i<=n;i++)
    {
        u=0;
        for(int j=1;j<=n;j++)
        {

            if(!vis[j]&&d[j]<d[u]) u=j;
        }
        vis[u]=1;
        cout<<u<<endl;
        ans+=d[u];//记录最小生成树的权值和
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&d[j]>ma[u][j]&&ma[u][j]!=-1)d[j]=ma[u][j];//更新两点距离最小的d
        }
    }
}

void dijkstra()
{
    memset(d,0x7f7f7f7f,sizeof(d));
    d[0]=0;
    int u;
    for(int i=1;i<=n;i++)
    {   u=n+1; //u初始为无穷大的点
        for(int j=0;j<n;j++)
        {
            if(!vis[j]&&d[j]<d[u]) u=j;
        }
        vis[u]=1;
        for(int j=0;j<n;j++)
        {
            if(!vis[j]&&d[u]+ma[u][j]<d[j])
            {
                d[j]=d[u]+ma[u][j];//区别所在
                p[j]=u;
            }
        }
    }
}
int main()
{

    cin>>n;
    int u,v,k;
    memset(ma,0x7f7f7f7f,sizeof(ma));
    for(int i=1; i<=n; i++)
    {
        cin>>u>>k;
        for(int j=1; j<=k; j++)
        {
            cin>>v>>ma[u][v];
        }
    }
    dijkstra();
    for(int i=0;i<n;i++)
    {
        cout<<i<<" "<<d[i]<<endl;
    }

    return 0;
}

优先队列优化Dijkstra算法

普通版的需要每次通过for循环找出最短路径,而有了优先队列,不必通过for循环可以直接拿出最短的路径。

#include <bits/stdc++.h>
using namespace std;
const int inf=0x7f7f7f7f;
const int maxn=10010;
int d[maxn],vis[maxn];//d存放最短路径长度,vis表示是否标记
int n,k,u;

vector<pair<int,int> > M[maxn];//采用邻接表
typedef pair<int,int> pa;//定义pair类型的数据类型
priority_queue<pa,vector<pa>,greater<pa> > q;//使用优先队列,使用最小堆形成的优先队列

void dijkstra()
{   //初始化
    memset(vis,0,sizeof(vis));
    memset(d,inf,sizeof(d));
    d[0]=0;
    q.push(make_pair(0,0));//将起始结点压入队列q

    while(!q.empty())
    {
        pair<int,int> t=q.top();//每次拿出最短路径
        q.pop();
        int u=t.second;//拿出u
        vis[u]=1;

        if(d[u]<t.first) continue;//别的点到t点的距离更短更新最开始到t点的距离,并且比最开始到u的路径短,所以这pair一定不是最短路径直接continue

        for(int j=0;j<M[u].size();j++)
        {
            int v=M[u][j].second;//取出到达点v
            if(d[v]>d[u]+M[u][j].first)
            {
                d[v]=d[u]+M[u][j].first;//更新d[v]
                q.push(make_pair(d[v],v));//将新的路径压入队列
            }
        }

    }
    for(int i=0;i<n;i++)
    {
        printf("%d %d\n",i,d[i]==inf?-1:d[i]);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&u,&k);
        for(int j=0;j<k;j++)
        {
            int v,c;
            scanf("%d%d",&v,&c);
            M[u].push_back(make_pair(c,v));//第一个int 存放权值,第二个存放结点编号
        }
    }
    dijkstra();
    return 0;
}

结构体版本:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef pair<int,int> pr;
int n,m;
vector <pr> M[maxn];//存图
int d[maxn],vis[maxn];
struct node //存放结点信息
{
    int id,d;
    node() {}
    node(int id,int d):id(id),d(d) {}
    inline bool operator<(const node b) const
    {
        return d>b.d;
    }
};

void dijkstra(int st)
{
    memset(vis,0,sizeof(vis));
    memset(d,0x7f7f7f7f,sizeof(d));
    priority_queue<node> q;
    d[st]=0;
    q.push(node(st,0));
    node t;
    while(!q.empty())
    {
        t=q.top();
        q.pop();
        if(vis[t.id])continue;//与if(d[u]<t.first) 代码含义相同,存放node的id相同但是d[id]值不同,我们已经更新了最小的d[id]所以不用在遍历
        vis[t.id]=1;//标记
        for(int i=0; i<M[t.id].size(); i++)
        {
            int j=M[t.id][i].first;
            if(d[j]>d[t.id]+M[t.id][i].second)
            {
                d[j]=d[t.id]+M[t.id][i].second;
                q.push(node(j,d[j]));
            }
        }
    }
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        M[u].push_back(make_pair(v,w));
    }
    dijkstra(1);
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",d[i]);
    }

    return 0;
}

复杂度分析:
普通版本:O(V^2)

每次要选出d值最小的顶点,一共V次操作,并且每个点要搜索与v相邻的的顶点,所以每个点要V次操作,一共V个点所以为O(V^2)

优先队列版本:O((V+E)logV)

每次从优先队列中取出路径最小的pair需要VlogV,每次更新路径需要遍历与该点相邻的点设有E个,在添加入堆的复杂度为logv总共需要Elogv的复杂度,所以一共需要VlogV+ElogV=(V+E)logV的复杂度。

例题
爱与愁商店最短路径

#include <bits/stdc++.h>

using namespace std;
const int maxn=210;
struct node
{

    int id;
    double v;
    node() {}
    node(int id,double v):id(id),v(v) {}
    bool operator<(const node b)const
    {
        return v>b.v;
    }
};
struct point
{
    int x,y;
} E[maxn];
vector<node>M[maxn];
double  d[maxn];
int vis[maxn];
int n,m,x,y,u,v;
double  dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void dijkstra(int start)
{
    fill(d+1,d+1+n,0x7f7f7f7f);
    memset(vis,0,sizeof(vis));
    priority_queue<node> q;
    q.push(node(start,0));//自己到自己的距离为0
    d[start]=0;
    node t;
    while(!q.empty())
    {
        t=q.top();
        q.pop();
        if(vis[t.id])continue;
        vis[t.id]=1;
        for(int i=0; i<M[t.id].size(); i++)
        {
            int u=t.id;
            int v=M[t.id][i].id;
            double w=M[t.id][i].v;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push(node(v,d[v]));
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&x,&y);
        E[i].x=x;
        E[i].y=y;
    }
    scanf("%d",&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        double k=dis(E[u],E[v]);
        M[u].push_back(node(v,k));
        M[v].push_back(node(u,k));
    }
    scanf("%d%d",&u,&v);
    dijkstra(u);
    printf("%.2f\n",d[v]);
    return 0;
}

链式前向星实现存图

#include <bits/stdc++.h>

#define ll long long
#define pr pair<double,int>
using namespace std;

const int maxn=2000+10;
int n,ans,ecnt,m;

double d[maxn],vis[maxn];
int X[maxn],Y[maxn];
int head[maxn];

struct node
{
    int u,v,next;
    double w;
} E[maxn];

void add(int u,int v,double w)
{
    E[++ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].w=w;
    E[ecnt].next=head[u];
    head[u]=ecnt;
}

priority_queue<pr,vector<pr>,greater<pr> > q;//注意最小堆是greater,默认以pair中first排序

double dis(int a,int b)
{
    return sqrt((X[a]-X[b])*(X[a]-X[b])+(Y[a]-Y[b])*(Y[a]-Y[b]));
}

void dijkstra(int u)
{
    memset(d,0x7f7f7f7f,sizeof(d));
    d[u]=0;
    q.push(make_pair(0,u));

    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i; i=E[i].next)
        {
            int j=E[i].v;
            if(!vis[j]&&d[j]>E[i].w+d[x])
            {
                d[j]=d[x]+E[i].w;
             //   cout<<"u"<<x<<"V"<<j<<"s"<<d[j]<<endl;
                q.push(make_pair(d[j],j));
            }
        }
    }
}



int main()
{

    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>X[i]>>Y[i];
    }
    cin>>m;
    int x,y;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y;
        add(x,y,dis(x,y));
        add(y,x,dis(x,y));
    }
    cin>>x>>y;
    dijkstra(x);
    printf("%.2lf",d[y]);

    return 0;
}

http://www.niftyadmin.cn/n/860359.html

相关文章

堆相关操作复杂度分析

堆相关操作复杂度分析

堆的层数 堆由一颗完全二叉树组成 那么n个结点的完全二叉树有log2(n1)层,近似等于log2n 解释一下为什么log2n层? 第一层2^0个元素 第二层2^1个元素 第三层2^2个元素 第h层2^(h-1)个元素 利用等比数列求和公式:2^0 2^1 2^2… 2^(h-1) 1x(1-2 ^ h) / (1-2) (2^h)-1个元素 这是…
阅读更多...
在layui中使用 jquery 触发select 的 change事件无效（转载）

在layui中使用 jquery 触发select 的 change事件无效（转载）

使用layui.use监听select事件 在使用layui框架时&#xff0c;原生的js onchange无法起效。要使用 layui.use([‘layer’, ‘jquery’, ‘form’], function () { var layer layui.layer, $ layui.jquery, form layui.form; <select lay-filter"demo" lay-veri…
阅读更多...
解析接口返回的json数组

解析接口返回的json数组

json串&#xff1a; {"message": "成功","hasMore": false,"result": 1,"count": 3,"records": [["72,064","项目主审","[00758]曾勇华","2020-09-08 09:53:00","…
阅读更多...
Floyed算法

Floyed算法

Floyed-Warshall算法定义 floyed主要解决多源最短路径问题,可以求出任意两点间的最短路径,以简单便捷著称! 适用于边值为负的情况。 实现过程 视频讲解 floyed的实质是动态规划思想(将小规模问题的解存储在内存中,等到大问题的解直接拿来有效利用,这就是动态规划的基本思路),f…
阅读更多...
layui框架中如何解决select onchange事件无效的问题

layui框架中如何解决select onchange事件无效的问题

layui将select改造了&#xff0c;所以直接写onchange无效 html代码如下,不要忘记 lay-filter属性 <param id"stationName" label"检测站名称" property"tsTestStation.name" input"select" input_id"station_name_for_vds&q…
阅读更多...
XMLGregorianCalendar类型的时间和String之间的转换

XMLGregorianCalendar类型的时间和String之间的转换

XMLGregorianCalendar类型的时间和String之间的转换 Calendar calendar approval.getFdCreateTime().toGregorianCalendar(); SimpleDateFormat sdf new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); sdf.setTimeZone(calendar.getTimeZone()); String dateString …
阅读更多...
Java集合如何删除某个元素

Java集合如何删除某个元素

Java集合如何删除某个元素 public static void main(String[] args) {List<String> strs new ArrayList<String>();List<String> removeStrs new ArrayList<String>();strs.add("one");strs.add("two");strs.add("three&q…
阅读更多...
最优贸易(SPFA反向图)

最优贸易(SPFA反向图)

题目: 题目传送门 C国有n个大城市和m 条道路&#xff0c;每条道路连接这 n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路&#xff0c;一部分为双向通行的道路&#xff0c;双向通行的道路在统计条数时也计为 1条。 …
阅读更多...
最新文章

Copyright @ 2022~2023