最短路-----dijkstra(单源最短路)

目录


一、dijkstra算法

求单源最短路算法,四种基本最短路算法中复杂度最低的,但不适用于含负权边的图。贪心思想,从起点到终点,一层层的遍历图。可以求从起点到任意一点的最短路。思想有点像prim(最小生成树算法)

1、算法:

先设立两个集合,S、Q。S集合用来存储已经确定最短路的点,Q集合用来存储未确定的点。

以下,我们用dist[]数组表示起点到各个点的距离。

然后开始演示:
首先,你有一个图(如何建图根据题意确定)

最短路-----dijkstra(单源最短路)
所有点的路径距离设置成∞,即dist[1~n] = ∞。起点的dist[1] 更新成 0(这是从自己家到自己家的距离!);
最短路-----dijkstra(单源最短路)

将第一个点链接的在Q集合中的点更新:要更新点的dist = min(该点的dist , 第一个点的dist + 边权)(松弛操作),同时让第一个点加入S集合;

最短路-----dijkstra(单源最短路)
选取Q集合中dist最小的点u。让与点u相连的、不在S集合中的点和点u进行松弛操作,并将点u加入S集合。然后重复此步骤,直到所有点都进入S集合。
最短路-----dijkstra(单源最短路)
最短路-----dijkstra(单源最短路)
最短路-----dijkstra(单源最短路)

最短路-----dijkstra(单源最短路)

最短路-----dijkstra(单源最短路)
最短路-----dijkstra(单源最短路)

当完成所有步骤后,图中的点的dist就是从起点到各个点的最短路了!

思想:

层层更新,每次选取距离S集合中的点最近的点进入S集合

2、代码实现

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long int ll;
const int N = 1e5+7;
const int INF = 1e9;
struct one_tu//链式前向星建图
{
    int v, w, next;
}tu[N];
int head[N],top,n,m;
void build(int u,int v,int w)
{
    top ++;
    tu[top] = {v, w, head[u]};
    head[u] = top;
}

struct node//设立一个优先队列
{
    bool friend operator < (node a, node b)
    {
        return a.cost > b.cost;//以cost从小到大排序(重载相反)
    }
    ll cost, to;//cost->存进队列的距离、to->点
};
int dist[N];//距离,用来存起始点到改点的距离
bool jud[N];//判断是否进入S队列

void dijkstra(int s)//dijkstra算法
{
    priority_queue <node> q;//建立优先队列
    for(int i = 1; i <= n; i++)
    {
        dist[i] = INF;//更新最大值
        jud[i] = false;//标记数据更新
    }
    dist[s] = 0;
    q.push({0,s});//初始点入队
    while(!q.empty())
    {
        ll u = q.top().to;
        q.pop();
        if(jud[u])continue;
        jud[u] = true;//将点u加入S集合
        for(int i = head[u]; i; i = tu[i].next)
        {
            int v = tu[i].v, w = tu[i].w;
            if(dist[v] > dist[u] + w)//松弛操作
            {
                dist[v] = dist[u] + w;
                if(!jud[v])//判断点v是否入队
                    q.push({dist[v],v});//点v入队
            }
        }
    }
}
//dist[N]数组最后会表示从起始点到1~n个点的最短路
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0; i <= m; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        build(u,v,w);//建图
    }
    dijkstra(1);
    
    printf("%d",dist[n]);
    return 0;
}

二、一些问题的说明

1、为什么dijkstra不能求带负权的路!

因为负权路可能会出现负环,dijkstra会出错,但只是错了,不会发生死循环什么的。除非代码写错了!!
先来一个图:

最短路-----dijkstra(单源最短路)
在这个图中你很容易就会发现,如果按照dijkstra算法跑的话,他会显示dist[5] = -6;但其实dist[5] = -10, dist[5] = -∞,实际上只要你多跑几圈,他的值会越来越小,所以完全可以跑成-∞;

2、如果没有负环,但有负权边可以吗?

答案是可以的。它不影响dijkstra的跑法。但是,如果你要测试它有没有负环,那为什么不用该算法跑它的最短路呢!

3、图上如果有负权边,如果我把所有的边权减去最小边权行不行?

答:不行!来,上图,来一个图就懂了!
最短路-----dijkstra(单源最短路)
对于这个图,如果想要把所有的边权加上同一个值,会导致最短路不是之前的那条!
每个边权-(-8)这样
原最短路:1->2->3->4这条边权就会+24,总边权就会变成30;
然而,新最短路是:1->5->4边权在更新过之后的总边权就会是7 + 16 = 23;
这样就懂了吧!他不行

4、如果我想要用dijkstra跑含负权的图怎么办

还真有办法!详情参见:Johnson
这个是我自己写的,主要还是上面的思想,真的很好!

上一篇:寒假每日学习总结D5


下一篇:最短路(Floyd,Dijkstra)