图---图的应用（最短路径）

适用有向 / 无向带权图约定边权非负Dijkstra含负权、无负环Floyd、Bellman-Ford顶点数 n邻接矩阵存储INF 代表无边一、单源最短路径Dijkstra 算法重点核心思想求某一个源点到其余所有顶点的最短路径贪心思想每次选距离源点最近、未确定的顶点松弛操作dist[v] min(dist[v], dist[u]G[u][v])适用边权 ≥ 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 算法最简单核心思想求任意两点之间最短路径动态规划G[i][j] min(G[i][j], G[i][k]G[k][j])k 为中转点暴力枚举所有中转可处理负权边不能有负环完整详细代码#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] (ij)?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单源・可负权核心思想适配负权边无法处理负环松弛 n−1 轮每条边都更新// 核心松弛代码 for(int k 1; k n-1; k) 遍历所有边(u,v,w) if(dist[v] dist[u]w) dist[v] dist[u]w;