Dijikstra算法

TLE_MLE_RE · 2024-04-14 14:01:00 · 算法·理论

Dijikstra算法

算法作用

Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）是一种求解非负权图上单源最短路径的算法。

过程

Dijikstra算法的步骤是：

1. 将节点分成两个集合：已确定最短路长度的点集（记为S 集合）的和未确定最短路长度的点集（记为T集合）。一开始所有的点都属于T集合。

2. 初始化dis(s)=0,其他的点dis均为+∞（这样便于待会比较）

3. 接下来，重复以下操作：

• 从 T 集合中，选取一个最短路长度最小的结点，移到 S 集合中。

• 对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作。

4. 直到t集合为空，算法结束

解释：松弛是什么？

以此图为例

从图中可以看到从3到1直接路径为6，但是如果以2为中转站，那么从3到1的路径就缩短为5

这个过程就叫松弛 Dijikstra算法的主要思想就是：通过“边”来松弛1号顶点到其余各个顶点的路程

栗子

邻接矩阵图

int[][] graph = new int[][]{
{0 , 2, ∞, 6}
{2 , 0, 3, 2}
{∞ , 3, 0, 2}
{6 , 2, 2, 0}};

参考代码

//这是暴力的代码，时间复杂度为 O(n^2) 
struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];

void dijkstra(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  for (int i = 1; i <= n; i++) {
    int u = 0, mind = 0x3f3f3f3f;
    for (int j = 1; j <= n; j++)
      if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];
    vis[u] = true;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
    }
  }
}

快乐结束