Dijkstra算法详解-创新互联

一、用途

Dijkstra算法是求最短路的方法之一，要求题目中边的权重都为非负数才可使用。目前有两种Dijkstra算法模板。

//下面n代表点数，m代表边数。

1.朴素版Dijkstra算法：时间复杂度O（n^2），适用于稠密图（点少边多），n^2和m是一个量级的。

面对稠密图我们使用的是邻接矩阵来存储信息。g[N][N]=W。W指的是权重。

例：g[a][b]=5,说明a到b的距离是5。

2.堆优化版Dijkstra算法：时间复杂度O（mlogn），适用于稀疏图（边和点差不多），m远小于n^2.

面对稀疏图我们使用邻接表来储存信息。

二、算法如何使用。

1.第一步：创建dist[N]数组来存储，第i个点到1号点的距离。初始时dist定义为无穷大，但dist[1]=0;

2.第二步：创建st[N]数组来存储已经找到最短路的点。st[i]为真，说明该点到1号点的最短距离已确定。若为假，则说明还未确定最短路径。初始化时，数组中各个元素为假。

3.第三步：遍历dist[N]数组，找到没有确定最短路径的节点中距离1号点最近的点。简单来说就是，找到一个不在st[N]数组里并且距离1号点最近的点。（暂且把这点叫做i点）

这样一来，i点的最短距离就确定了。（此处的i点的最短距离一定等于dist[i]，这有关Dijkstra算法的数学原理，有兴趣可以查查）

既然i点最短距离确定了，自然要将i点放到st[N]数组里去了。

4.第四步：运用找到的i点，去更新所有点的最短距离。

代码：for(int j=1;j<=n;j++)

dist[j]=min(dist[i],g[i][j]);

5.第五步：重复三、四步骤n-1次，则所有的点都可以找到最短路径。（因为每一次都会找到一个i点，并将它放进st[N]数组，重复n-1次就确定了所有的点）

三、举个简单例子

如下图：

1.  先开始，所有点都没有找到最短距离所以st[N]所有元素都是false，除1号点外，其他的距离全是∞。

  找到距离1号点最近，且不在st[N]数组内的点，发现1号点就是要找的点。因为dist[1]最小，并且st[1]=false。

  所以用1号点去更新所有的点距离。

 dist[2]=min(dist[2],dist[1]+g[1][2]);

  dist[3]=min(dist[3],dist[1]+g[1][3]);

2.此时变成了

重复步骤，找到距离1号点最近，且不在st[N]数组内的点，发现2号点是我们要找的。

所以用2号点更新所有点的距离。

dist[1]=min(dist[1],dist[2]+g[2][1]);

dist[3]=min(dist[3],dist[2]+g[2][3]);

3.得到最终结果

四、例题

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1号点到 n 号点的最短距离，如果无法从 1号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x到点 y的有向边，边长为 z。

输出格式

输出一个整数，表示 1号点到 n号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n≤500
1≤m≤100000,
图中涉及边长均不超过10000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

五、例题题解

  重边和自环如何解决？

  1.重边：我们可以取重边中最小的一条边。g[a][b]=min(g[a][b],c)；

  2.自环：本题对自环没有影响，因为dist[j]=min(dist[j],dist[t]+g[t][j]);

t==j时g[j][j]，代表的就是自环，只要自环是非负的，dist[j]的值就不会改变。

代码:

#include
#include
#include
using namespace std;

const int N=510;

int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定

int n,m;

int Dijkstra()
{
  memset(dist, 0x3f,sizeof dist);     //初始化距离  0x3f代表无限大

  dist[1]=0;  //第一个点到自身的距离为0

  for(int i=0;i   {
  int t=-1;       //t存储当前访问的点

  for(int j=1;j<=n;j++)   //这里的j代表的是从1号点开始
  if(!st[j]&&(t==-1||dist[t]>dist[j]))     
  t=j;

  st[t]=true;   

  for(int j=1;j<=n;j++)           //依次更新每个点所到相邻的点路径值
  dist[j]=min(dist[j],dist[t]+g[t][j]);
  }

  if(dist[n]==0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最低路径
  return dist[n];
}
int main()
{
  cin>>n>>m;

  memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径
  //所以每个点初始为无限大

  while(m--)
  {
  int x,y,z;
  cin>>x>>y>>z;
  g[x][y]=min(g[x][y],z);     //如果发生重边的情况则保留最短的一条边
  }

  cout<   return 0;

}

借用一下Acwing平台上yxc大佬的代码。。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧