目录
一、dijkstra算法
求单源最短路算法,四种基本最短路算法中复杂度最低的,但不适用于含负权边的图。贪心思想,从起点到终点,一层层的遍历图。可以求从起点到任意一点的最短路。思想有点像prim(最小生成树算法)
1、算法:
先设立两个集合,S、Q。S集合用来存储已经确定最短路的点,Q集合用来存储未确定的点。
以下,我们用dist[]数组表示起点到各个点的距离。
然后开始演示:
首先,你有一个图(如何建图根据题意确定)
所有点的路径距离设置成∞,即dist[1~n] = ∞。起点的dist[1] 更新成 0(这是从自己家到自己家的距离!);
将第一个点链接的在Q集合中的点更新:要更新点的dist = min(该点的dist , 第一个点的dist + 边权)(松弛操作),同时让第一个点加入S集合;
选取Q集合中dist最小的点u。让与点u相连的、不在S集合中的点和点u进行松弛操作,并将点u加入S集合。然后重复此步骤,直到所有点都进入S集合。
当完成所有步骤后,图中的点的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算法跑的话,他会显示dist[5] = -6;但其实dist[5] = -10, dist[5] = -∞,实际上只要你多跑几圈,他的值会越来越小,所以完全可以跑成-∞;
2、如果没有负环,但有负权边可以吗?
答案是可以的。它不影响dijkstra的跑法。但是,如果你要测试它有没有负环,那为什么不用该算法跑它的最短路呢!
3、图上如果有负权边,如果我把所有的边权减去最小边权行不行?
答:不行!来,上图,来一个图就懂了!
对于这个图,如果想要把所有的边权加上同一个值,会导致最短路不是之前的那条!
每个边权-(-8)这样
原最短路:1->2->3->4这条边权就会+24,总边权就会变成30;
然而,新最短路是:1->5->4边权在更新过之后的总边权就会是7 + 16 = 23;
这样就懂了吧!他不行
4、如果我想要用dijkstra跑含负权的图怎么办
还真有办法!详情参见:Johnson
这个是我自己写的,主要还是上面的思想,真的很好!