Dijkstra算法

liyao2025 · 2025-01-10 23:47:53 · 算法·理论

首先，给出模板

:::success[Dijkstra]

struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  memset(vis, 0, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

:::

最短路径

路径长度: 当图是带权图时，把从一个顶点i到图中其余任意一个顶点j的一条路径(可能不止一条)所经过边上的权值之和，定义为该路径的带权路径长度。
最短路径: 把带权路径长度最短的那条路径称为最短路径。

备注:求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。

带权有向图G的最短路径问题一般可分为两类: (1)单源最短路径:求图中某一顶点到其他各顶点的最短路径。 (2)多源最短路径:求每对顶点间的最短路径。

单源最短路径-Dijkstra算法(迪杰斯特拉)

(1) Dijkstra整体思路:

Dijkstra算法设置一个集合S记录已求得的最短路径的顶点，初始时把源点v_0放入S，集合S每并入一个新顶点v_i，都要修改源点v_0到集合V-S中顶点当前的最短路径长度值

(2) 些符号说明:

邻接矩阵$arcs$表示带权有向图，$arcs[i][j]$表示有向边$<i,j>$的权值，若不存在有向边$<i,j>$则$arcs[i][j]$为$∞$。

(3) Dijkstra算法流程: (求解vo到其他节点的最短路径)

1) 初始化:集合S初始为{0}，dist[]的初始值dist[i]=arcs[0][i], i=1,2…, n-1

2) 2)从顶点集合V-S中选出vj,满足dist[j]=Min{dist[i] | i \in V-S},v_j就是当前求得的一条从v_0出发的最短路径的终点，令S=S U {j} 3) 修改从v_0出发到集合V-S上任一顶点v_k可达的最短路径长度:若

4)重复2)-3)操作共n-1次，直到所有的顶点都包含在S中。备注:步骤3举例: 如下图所示，源点为vo，初始时S={vo},dist[1]=3,dist[2]=7,当将v1并入集合S后， dist[2]需要更新为4。 ![](https://oss-liuchengtu.hudunsoft.com/userimg/f2/f24ada253280a50a3d99cf45fa69882a.PNG) ### (4)模拟Dijkstra的过程 - 图解 ![](https://oss-liuchengtu.hudunsoft.com/userimg/aa/aaa3063bacb88dc93e4a1e7b78e88157.PNG) - 表格方式 ![](https://oss-liuchengtu.hudunsoft.com/userimg/44/447d1f0b809928d91ad337b8daaebc5a.PNG) - 文字描述初始化:集合$S$初始为${v_i}$，$v_1$可达$v_2$和$v_3$,$v_1$不可达$v_3$和$v_4$，因此$dist[]$数组各元素的初值依次设置为$dist[2]=10， dist[3]=∞,dist[4]=∞,dist[5]=5$。第一轮:选出最小值$dist[5]$，将顶点$v_5$并入集合$S$，即此时已找到$v_1$到$v_5的最短路径。当$v_5$加入$S$后,从$v_1$到集合$V-S$中可达顶点的最短路径长度可能会产生变化,因此需要更新$dist[]

数组。v_5可达v_2,因v_1→v_5→v_2的距离8比dist[2]=10小,更新dist[2]=8;v_5可达v_3, V_1→V_5→V_2→V_3的距离 14，更新dist[3]=14 ;v_5可达 v_4，V_1→V_5→V_4的距离 7，更新 dist[4]=7.

第二轮:选出最小值dist[4]，将顶点v_4并入集合S。继续更新dist[]数组。v_4不可达

第三轮:选出最小值$dist[2]$，将顶点$v_2$并入集合$S$。继续更新$dist[]$数组。$v_2$可达$V_3$,$v_1→v_5→v_2→v_3$的距离$9$比$dist[3]$小，更新 $dist[3]=9

第四轮:选出唯一最小值dist[3]，将顶点v_3并入集合S，此时全部顶点都已包含在S中。

(5)时间复杂度分析

邻接矩阵存储图:0(|V|^2) 邻接表存储图:0(|V|^2)(虽然修改dist[]的时间可以减少，但由于在dist[]中选择最小分量的时间不变)

(6)不适用条件

当图中含有负权边时，Dijkstra算法将不适用。(Dijkstra算法是基于贪心的)。