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

图论算法讲解--最短路--Dijkstra算法

程序员文章站 2023-12-23 11:02:40
...

一.绪论

要学习最短路算法我们首先应该知道什么是图以及什么是最短路。

图在离散数学中的定义为:图G=(V,E)是一个二元组(V,E)使得E⊆[V]的平方,所以E的元素是V的2-元子集。为了避免符号上的混淆,我们总是默认V∩B=Ø。集合V中的元素称为图G的定点(或节点、点),而集合E的元素称为边(或线)。通常,描绘一个图的方法是把定点画成一个小圆圈,如果相应的顶点之间有一条边,就用一条线连接这两个小圆圈,如何绘制这些小圆圈和连线时无关紧要的,重要的是要正确体现哪些顶点对之间有边,哪些顶点对之间没有边。

简单来讲,一个图就是由两个集合构成,集合V储存图中的所有顶点,集合E储存图中所有的边。

最短路的定义为:在一个图中,每条边都有一个权值,给出一个起点和终点,求出起点到终点之间权值最小的路径,即是最短路。


二.Dijkstra概述

Dijkstra算法用于解决单源最短路问题,所谓单源最短路就是指定一个起点,求出这个起点到其它所有点的最短路。
使用Dijkstra算法还要求图中不能有权值为负的边,否则会出现死循环。


三.Dijkstra算法流程

首先给出几个定义:

1.s:表示单源最短路的起点。
2.d[v]:表示从起点到v点的距离,初始化d[1~n]=inf,d[s]=0,当Dijkstra算法结束后,d[v]所存储的即时由起点到v的最短路长度。
3.vst[v]:记录顶点v是否已经更新过,初始化vst[1~n]=0,表示所有点都未被更新过。
4.val(u,v):表示从u点连向v点边的权值。

算法流程:

1.从图中找出所有u可达的顶点v0~vm,对于v0~vm,若有d[v]> d[u]+val(u,v),则表示发现更短的路线,更新d[v]为d[u]+val(u,v)。
2.找出d[v]最小,且vst[v]=0的点,让v作为新的起点,将vst[v]=1,表示顶点v已被更新。
3.重复上述过程,直到所有顶点都被更新。

从上述流程中不难发现,所谓Dijkstra算法,就是依次让每个顶点作为起点,更新最短路的过程。
具体过程,请结合算法流程来看图文演示,相信看完之后大家一定会理解Dijkstra算法的思想。


四.图文演示

1.
图论算法讲解--最短路--Dijkstra算法
初始状态,将d[1~n]=inf,d[s]=0
以点M作为起点,即s=M

d数组:        vst数组:
d[M]=0       vst[M]=0
d[W]=inf     vst[W]=0
d[E]=inf      vst[E]=0
d[D]=inf      vst[D]=0
d[X]=inf      vst[X]=0


2.
图论算法讲解--最短路--Dijkstra算法
d数组:        vst数组:
d[M]=0       vst[M]=0
d[W]=inf     vst[W]=0
d[E]=inf      vst[E]=0
d[D]=inf      vst[D]=0
d[X]=inf      vst[X]=0

找出d中值最小且未被使用的点,发现d[M]=0最小,且vst[M]=0,未被使用,故将M作为新的起点
找出所有M可达的顶点,为X、W、E
d[X]=inf > 0+10 ,更新d[X]=10
d[W]=inf > 0+5 ,更新d[W]=5
d[E]=inf > 0+8 ,更新d[E]=8
M已被使用,vst[M]=1


3.
图论算法讲解--最短路--Dijkstra算法
d数组:       vst数组:
d[M]=0      vst[M]=1
d[W]=5      vst[W]=0
d[E]=8       vst[E]=0
d[D]=inf     vst[D]=0
d[X]=10     vst[X]=0

找出d中值最小且未被使用的点,发现d[W]=5最小,且vst[W]=0,未被使用,故将W作为新的起点
找出所有W可达顶点,为M、X、D、E
vst[M]=1,已被更新过,故忽略
d[X]=10 > 5+3 ,更新d[X]=8
d[D]=inf > 5+9 ,更新d[D]=14
d[E]=8 >5+2 ,更新d[E]=7
W已被使用,vst[W]=1


4.
图论算法讲解--最短路--Dijkstra算法
d数组:       vst数组:
d[M]=0      vst[M]=1
d[W]=5      vst[W]=1
d[E]=7       vst[E]=0
d[D]=14     vst[D]=0
d[X]=8       vst[X]=0

找出d中值最小且未被使用的点,发现d[E]=7最小,且vst[E]=0,未被使用,故将E作为新的起点
找出所有E可达的顶点,为W、M、D
vst[W]=1,已被更新过,忽略
vst[M]=1,已被更新过,忽略
d[D]=14 > 7+6 ,更新d[D]=13
E已被使用,vst[E]=1


5.
图论算法讲解--最短路--Dijkstra算法
d数组:       vst数组:
d[M]=0      vst[M]=1
d[W]=5      vst[W]=1
d[E]=7       vst[E]=1
d[D]=13     vst[D]=0
d[X]=8       vst[X]=0

找出d中值最小且未被使用的点,发现d[X]=8最小,且vst[X]=0,未被使用,故将X作为新的起点
找出所有X可达的顶点,为W、M、D
vst[W]=1,已被更新过,忽略
vst[M]=1,已被更新过,忽略
d[D]=13 >8+1 ,更新d[D]=9
X已被使用,更新vst[X]=1


6.
图论算法讲解--最短路--Dijkstra算法
d数组:       vst数组:
d[M]=0      vst[M]=1
d[W]=5      vst[W]=1
d[E]=7       vst[E]=1
d[D]=9       vst[D]=0
d[X]=8       vst[X]=1

找出d中值最小且未被使用的点,发现d[D]=9最小,且vst[D]=0,未被使用,故将D作为新的起点
找出所有D可达的顶点,为E、W、X
vst[E]=1,已被使用,忽略
vst[W]=1,已被使用,忽略
vst[X]=1,已被使用,忽略
D已被使用,更新vst[D]=1


7.
d数组:       vst数组:
d[M]=0      vst[M]=1
d[W]=5      vst[W]=1
d[E]=7       vst[E]=1
d[D]=9       vst[D]=1
d[X]=8       vst[X]=1

发现所有顶点都被使用过,算法结束,此时d数组中保存的就是以M为起点,到达所有其它点的单源最短路长度

五.算法实现及优化

致此,我相信大家都理解了算法的流程了,下面通过代码来看如何具体实现Dijkstra,详见注释。

普通版本:O(n^2)

#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;

const int maxv=1000;
const int inf=0x3f3f3f3f;
int cost[maxv][maxv];       //邻接矩阵存图
int d[maxv];
bool vst[maxv];
int N;                 //顶点的个数

void dijkstra(int s)
{
    memset(d,inf,sizeof(d));     //初始化d[1~N]=inf
    d[s]=0;                     //初始化d[s]=0
    fill(used,used+v,false);       //初始化vst[1~N]=0

    while(true)
    {
        int now=-1;
        for(int u=0;u<N;u++)
        {
            if(!used[u]&&(now==-1||d[u]<d[now])) //找到d最小,且vst=0的点作为新的起点
                now=u;
        }
        if(now=-1) break;           //now未被更新,即表示所有顶点都被使用过,算法结束

        for(int v=0;v<N;v++)        //遍历当前起点now能到达的所有点
        {
            if(d[v]>d[now]+cost[now][v])     //若d[v]>d[u]+val(u,v),则更新
                d[v]=d[now]+cost[now][v]
        }
        vst[now]=1;             //当前起点now已被使用过,vst[now]=1
    }
}

路径还原:

除了最短路的长度,还要求出最短路的路径

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int maxv=1000;
const int inf=0x3f3f3f3f;
int cost[maxv][maxv];       //邻接矩阵存图
int prev[maxv];          //储存前驱点编号,是路径还原的关键
int d[maxv];
bool vst[maxv];
int N;                 //顶点的个数

void dijkstra(int s)
{
    memset(d,inf,sizeof(d));     //初始化d[1~N]=inf
    d[s]=0;                     //初始化d[s]=0
    fill(used,used+v,false);       //初始化vst[1~N]=0

    while(true)
    {
        int now=-1;
        for(int u=0;u<N;u++)
        {
            if(!used[u]&&(now==-1||d[u]<d[now])) //找到d最小,且vst=0的点作为新的起点
                now=u;
        }
        if(now=-1) break;           //now未被更新,即表示所有顶点都被使用过,算法结束

        for(int v=0;v<N;v++)        //遍历当前起点now能到达的所有点
        {
            if(d[v]>d[now]+cost[now][v])     //若d[v]>d[u]+val(u,v),则更新
            {
                d[v]=d[now]+cost[now][v];
                prev[v]=now;                 //同时更新前驱结点编号
            }
        }
        vst[now]=1;             //当前起点now已被使用过,vst[now]=1
    }
}
vector <int>get_path(int t)         //路径还原函数,将最短路径存在path中
{
    vector<int>path;
    for(;t!=-1;t=prev[t])
        path.push_back(t);
    reverse(path.begin(),path.end());
    return path;
}

优先队列优化:O(ElogV)

#include <bits/stdc++.h>
#include <vector>
#include <queue>
using namespace std;

const int MAX_N=1000;
const int MAX_V=1000;
const int INF=0x3f3f3f3f;
struct edge
{
    int to,cost;
};
typedef pair<int,int>P;    //first是最短距离,second是顶点编号
int N;                     //顶点的个数
vector<edge>G[MAX_N];       //存图的方法有很多种,大家可以用自己喜欢的方式
int d[MAX_V];

void Dijstra(int s)
{
    //通过指定greater<P>参数,堆按照first从小到大顺序取出值
    priority_queue< P,vector<P>,greater<P> > que;
    fill(d,d+N,INF);       //初始化,d[1~N]设为inf
    d[s]=0;               //初始化,d[s]=0
    que.push(P(0,s));
    while(!que.empty())
    {
        P now=que.top();         //now表示当前起点
        que.pop();
        int u=now.second;
        if(d[u]<now.first) continue;
        for(int i=0;i<G[u].size();i++)       //遍历当前起点能到达的所有点
        {
            edge e=G[u][i];
            if(d[e.to]>d[u]+e.cost)         //如果d[v]>d[u]+val(u,v)则更新
            {
                d[e.to]=d[u]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}
相关标签: ACM

上一篇:

下一篇: