企业官网建设流程全解析

🔥keyipatience:个人主页

🎬作者简介：C/C++后端开发学习者

🌟专栏传送门：《c++》《linux》《c++高阶数据结构》《c++数据结构与算法》

⭐️patience is key in life

Dijkstra（邻接矩阵版，(O(n^2)）核心工作：

前提：无负权

1. 维护三组数组：
   • dist[]：源点到每个顶点当前预估最短距离
   • vis[]：标记顶点是否已经确定最短路径
   • ppath[]：记录每个点的前驱顶点，用于还原路径
2. 重复 n 轮（顶点总数）： ① 在还没确定最短路径的顶点中，选出预估距离dist最小的顶点 u； ② 标记vis[u]=true，锁定 u 的最短距离（无负权边保证不会有更短路径）； ③松弛：用 u 去更新它所有邻接点。如果源→u→邻点比之前记录的距离更短，就更新距离，同时记录前驱。
3. 最终得到源点到全部顶点的最短距离，借助前驱数组反向回溯，就能得到完整路径。

一句话速记：每次挑离源点最近的未确定点，锁定它，再拿它去更新邻居的预估最短距离。

一步步代码实现：

void Dijkstra(const V& src, vector<W>& dist, vector<int>& ppath) {

函数作用：传入源点 src，输出 dist 最短距离数组、ppath 前驱数组

第 1 段：获取顶点、初始化变量

int n = _vertexs.size(); int srci = GetVertexIndex(src); dist.resize(n, MAX_W); ppath.resize(n, -1); vector<bool>vis(n, false); dist[srci] = W();

1. n = _vertexs.size()：拿到图里顶点总个数
2. srci = GetVertexIndex(src)：把源点名字（比如 "A"）转成数组下标
3. dist.resize(n, MAX_W)：dist 数组全部初始成无穷大，表示暂时不可达
4. ppath.resize(n, -1)：前驱数组，全部 - 1，代表暂时没有前驱
5. vector<bool>vis(n, false)：标记数组，false = 该点最短路径还没确定
6. dist[srci] = W()：源点到自己距离为 0

第 2 段：外层主循环（循环 n 次，每次确定 1 个点）

for (int i = 0; i < n; i++) {

一共有 n 个顶点，最多需要选 n 次，每一轮选出 1 个点，确定它的最短路径

子段 A：贪心查找，找未访问中 dist 最小的点 u

W min = MAX_W; int u = 0; for (int j = 0; j < n; j++) { if (!vis[j] && dist[j] < min) { min = dist[j]; u = j; } }

• min：用来记录当前最小距离
• u：保存找到的顶点下标
• j 遍历全部顶点
• 条件：!vis[j]（这个点还没确定最短路径）并且 dist [j] 比当前 min 更小
• 满足就更新 min，记录 u

作用：挑出当前离源点最近，还没确定的点 u

vis[u] = true;

核心！标记 u，u 的最短路径确定，后续不再改动

子段 B：松弛操作，用 u 更新其他点

for (int k = 0; k < n; k++) { if (_matrix[u][k] != MAX_W && !vis[k] && dist[u] + _matrix[u][k] < dist[k]) { dist[k] = dist[u] + _matrix[u][k]; ppath[k] = u; } } } }

k 遍历所有顶点：

1. _matrix[u][k] != MAX_W：u 到 k 存在边
2. !vis[k]：k 还没有确定最短路径
3. dist[u] + _matrix[u][k] < dist[k]：走「源→u→k」比原来记录的更近

三个条件全满足：

• 更新 dist [k] 为更短的距离
• ppath[k]=u：记录 k 的前驱是 u，后面用来回溯路径

配套：路径打印函数分段讲解

void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& ppath) { int srci = GetVertexIndex(src); int n = _vertexs.size();

拿到源点下标，顶点总数

for (int i = 0; i < n; i++) { vector<int>path; int parent = i;

遍历每一个终点 i；path 存路径；parent 从终点 i 开始反向找

while (parent!=srci) { path.push_back(parent); parent = ppath[parent]; } path.push_back(srci);

循环：不断找 parent 的前驱，直到追到源点；出循环后把源点放进 path。

此时 path 是逆序：终点 → ... → 源点

reverse(path.begin(), path.end());

反转数组，变成正向：源点 → ... → 终点

for (auto e : path) { cout << _vertexs[e] << "->"; } cout << dist[i] << endl; } }

循环输出路径上每个顶点，最后输出这条路径的最短距离。

整体代码：

void Dijkstra(const V& src, vector<W>& dist, vector<int>& ppath) { int n = _vertexs.size(); int srci = GetVertexIndex(src); dist.resize(n, MAX_W);//dist[]的含义：目前我们已经探索过的路径里，起点 s 到这个点的最短距离 ppath.resize(n, -1); // 初始化ppath数组全部为-1 vector<bool>vis(n, false); dist[srci] = W();//源点到自己的 为0； //ppath[srci] = srci; //一共有n个顶点要走n次 for (int i = 0; i < n; i++) { W min = MAX_W; int u = 0; for (int j = 0; j < n; j++) { if (!vis[j] && dist[j] < min) { min = dist[j]; u = j; } } //贪心！！为什么不选10，要选5，为什么可以把vis[y]=true锁死，确定一定是最短的 vis[u] = true; //松弛 for (int k = 0; k < n; k++) { //如果srci->u + u->k 比 srci->k更短 则进行更新 if (_matrix[u][k] != MAX_W && !vis[k] && dist[u] + _matrix[u][k] < dist[k]) { //!vis[k]k 已经确定最短路径的话，就不用再松弛它了， //一旦 vis [k]=true，k 的最短路径就确定死了，再也不会变短。 //!!! dist[k] = dist[u] + _matrix[u][k]; ppath[k] = u; } } } } void PrinrtShotPath(const V& src, const vector<W>& dist, const vector<int>& ppath) { int srci = GetVertexIndex(src); int n = _vertexs.size(); for (int i = 0; i < n; i++) { vector<int>path; int parent = i;//下面要打印dist[i]所以不要动i while (parent!=srci) { path.push_back(parent); parent = ppath[parent]; } path.push_back(srci); reverse(path.begin(), path.end()); for (auto e : path) { cout << _vertexs[e] << "->"; } cout << dist[i] << endl; } }

测试例子：

void TestGraphDijkstra() { const char* str = "syztx"; Graph<char, int, INT_MAX, true> g(str, strlen(str)); g.AddEdge('s', 't', 10); g.AddEdge('s', 'y', 5); g.AddEdge('y', 't', 3); g.AddEdge('y', 'x', 9); g.AddEdge('y', 'z', 2); g.AddEdge('z', 's', 7); g.AddEdge('z', 'x', 6); g.AddEdge('t', 'y', 2); g.AddEdge('t', 'x', 1); g.AddEdge('x', 'z', 4); vector<int> dist; vector<int> parentPath; g.Dijkstra('s', dist, parentPath); g.PrinrtShotPath('s', dist, parentPath); }

结果：

贪心为什么不选10要选5，即为什么选dist最小的？并且就能直接锁定5就是最短的？为什么不能有负权值？

贪心规则：在还没锁定的点（就是vis[i]为假）里面，选 dist 最小的那个！

第一轮的时候：

W min = MAX_W; size_t u = 0; //遍历j=0~4 j=0：S[j]=false，dist[0]=0 < MAX_W min=0，u=0 j=1：S=false，dist=MAX_W，不小于0，跳过 j=2：S=false，dist=MAX_W，跳过 j=3：S=false，dist=MAX_W，跳过 j=4：S=false，dist=MAX_W，跳过

s的dist=0，min=0，选s源点

第二轮的时候：

W min = MAX_W; size_t u=0; j=0: S=true，跳过 j=1: S=false，dist[1]=5 < MAX_W → min=5, u=1 j=2: dist=MAX_W，不更新 j=3: dist=10，10<5不成立 j=4: dist=MAX_W

y 的 dist = 5

t 的 dist =10 5 < 10，所以选 y，不选 t。

为什么要这样？

先看这张图第二轮的状态

起点 s 已经被涂黑（放进集合 S，S [s]=true） dist 数组：

• s：0（锁定）
• y：5 （s→y，边权 5）
• t：10（s→t，边权 10）
• z：∞
• x：∞

剩下没有涂黑（S=false）的顶点：y、t、z、x 它们的预估 dist：y=5，t=10，z = 无穷，x = 无穷

假设：存在一条路径 s→…→v → y，总长度 < 5（也就是有一条更短的路到 y）

1.这条路径，在到达 y 之前，最后经过的点叫 v，v 一定是不在 S 里面（没涂黑）的点。

因为s→…→v → y是一条更短的路，如果v在S里面已经就用来松弛更新dist[v]了。

2.这条假设路径总长度 = dist [v] + w (v→y) 因为边权 w ≥ 0，所以： dist [v] + w (v→y) ≥ dist [v]

我们假设整条路径长度 < 5，代入上面不等式： 5 > dist [v] + w (v→y) ≥ dist [v] 可以推出： dist [v] < 5

矛盾！当前所有未涂黑的点： y (5)、t (10)、z (∞)、x (∞) 没有任何一个未涂黑的 v，dist [v] 是小于 5 的。 我们假设的这个 v 根本不存在，也就不存在这条比 5 还短的路径

为什么负权边的时候，上面这套推理直接失效？、

核心：w 可以是负数，dist[v]+w(v→y) ≥ dist[v]这个不等式不再成立！

如果 w (v→y) 是负数：

dist [v] + w (v→y)< dist [v]

举个例子： 假设 v就是 t，dist [t]=10，有一条边 t→y，权值-7那么dist[t] + (-7) =10-7=3 <5

也就是： 哪怕所有未锁定点的 dist 全都 ≥5，依然可以配上一条负边，得到一条更短的到 y 的路径。 那我们就不能保证 dist [y]=5 是真实最短路径，不能提前锁定 y。

所以这个算法必须保证权值不能有负数

对比 t 为什么不能锁

t 现在dist=10。 候选集合里还有 y，y 的dist=5，比 10 更小。 y 还没被锁定，y 到 t 有边。 后面把 y 选中、加入 S 之后，就会松弛：dist[y]+w(y→t)，算出来 8，能把 t 的距离从 10 更新成更小的 8。所以现在还不能锁定

宏观整体理解

前提：所有边权 ≥ 0（无负权边）

一旦选出 u（注意是未访问点里 dist 最小的），不可能后面再找到一条更短路径到 u因为后面任何其他点到 u 的路径，都要经过其他点，而其他点的 dist 本身就≥dist [u]（dist[u]就是未访问点最小的），再加正数边权只会更大。 → 所以 u 的最短距离永久确定，打上 vis 标记，不再处理。如果有负权边，这个结论直接失效，Dijkstra 不能用。