企业官网建设流程全解析

适用：有向 / 无向带权图约定：

• 边权非负：Dijkstra
• 含负权、无负环：Floyd、Bellman-Ford
• 顶点数 n，邻接矩阵存储，INF 代表无边

一、单源最短路径：Dijkstra 算法（重点）

核心思想

1. 求某一个源点到其余所有顶点的最短路径
2. 贪心思想：每次选距离源点最近、未确定的顶点
3. 松弛操作：dist[v] = min(dist[v], dist[u]+G[u][v])
4. 适用：边权 ≥ 0

完整详细代码 + 注释

#include <stdio.h> #include <string.h> #define INF 0x3f3f3f3f #define MAXN 105 int G[MAXN][MAXN]; // 邻接矩阵 int dist[MAXN]; // 源点到各点最短距离 int vis[MAXN]; // 是否确定最短距离 int n, m; // start：源点 void Dijkstra(int start) { // 1.初始化 memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; i++) dist[i] = G[start][i]; vis[start] = 1; // 源点直接确定 // 循环 n-1 次，确定剩余所有点 for(int k = 1; k < n; k++) { // 2.选距离最小且未访问的点 u int min = INF, u; for(int i = 0; i < n; i++) { if(!vis[i] && dist[i] < min) { min = dist[i]; u = i; } } vis[u] = 1; // 标记为已确定 // 3.松弛更新：借 u 走中转更短 for(int v = 0; v < n; v++) { if(!vis[v] && G[u][v] != INF) { if(dist[v] > dist[u] + G[u][v]) dist[v] = dist[u] + G[u][v]; } } } } int main() { scanf("%d%d", &n, &m); // 矩阵初始化 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) G[i][j] = (i == j) ? 0 : INF; // 建图 for(int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u][v] = w; } Dijkstra(0); // 以0号为源点 // 输出结果 for(int i = 0; i < n; i++) { if(dist[i] == INF) printf("0->%d：不可达\n", i); else printf("0->%d：%d\n", i, dist[i]); } return 0; }

复杂度

O(n2)，稠密图优选

二、多源最短路径：Floyd 算法（最简单）

核心思想

1. 求任意两点之间最短路径
2. 动态规划：G[i][j] = min(G[i][j], G[i][k]+G[k][j])
3. k 为中转点，暴力枚举所有中转
4. 可处理负权边，不能有负环

完整详细代码

#include <stdio.h> #define INF 0x3f3f3f3f #define MAXN 105 int G[MAXN][MAXN]; int n, m; void Floyd() { // k：中转点 for(int k = 0; k < n; k++) // i：起点 for(int i = 0; i < n; i++) // j：终点 for(int j = 0; j < n; j++) { if(G[i][k] < INF && G[k][j] < INF) { if(G[i][j] > G[i][k] + G[k][j]) G[i][j] = G[i][k] + G[k][j]; } } } int main() { scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) G[i][j] = (i==j)?0:INF; for(int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u][v] = w; } Floyd(); // 输出任意两点最短距离 for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(G[i][j]==INF) printf("∞ "); else printf("%d ",G[i][j]); } printf("\n"); } return 0; }

复杂度

O(n3)，适合顶点少的小图

三、Bellman-Ford（单源・可负权）

核心思想

1. 适配负权边，无法处理负环
2. 松弛 n−1 轮，每条边都更新

   // 核心松弛代码 for(int k = 1; k <= n-1; k++) 遍历所有边(u,v,w) if(dist[v] > dist[u]+w) dist[v] = dist[u]+w;