33DAI：批量导入三三文档

2026-05-20T18:24:06Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第124行：		第124行：
	[[Category:图论]]		[[Category:图论]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:24Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 最短路 ==

最短路径问题：给定带权图，求两点间权值和最小的路径。

== Floyd 算法 ==

全源最短路。动态规划思想，枚举中间点进行松弛。

<syntaxhighlight lang="cpp">
int dis[MAXN][MAXN]; // dis[i][j] = i 到 j 的最短距离，初始为 INF

for (int i = 1; i <= n; i++)
dis[i][i] = 0;

void floyd(int n)
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
</syntaxhighlight>

时间复杂度：<math>O(n^3)</math>，适合 <math>n \le 500</math>。

== Dijkstra 算法 ==

单源最短路，适用于'''非负边权'''图。每次选当前距离最小的点松弛邻点。

=== 暴力版 ===

<syntaxhighlight lang="cpp">
int dis[MAXN];
bool vis[MAXN];

void dijkstra(int s)
{
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
for (int i = 1; i <= n; i++)
{
int u = 0;
for (int j = 1; j <= n; j++)
if (!vis[j] && (u == 0 || dis[j] < dis[u]))
u = j;
vis[u] = true;
for (auto [v, w] : g[u])
if (!vis[v])
dis[v] = min(dis[v], dis[u] + w);
}
}
</syntaxhighlight>

时间复杂度：<math>O(n^2)</math>。

=== 优先队列优化版 ===

<syntaxhighlight lang="cpp">
void dijkstra(int s)
{
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, s});

while (!pq.empty())
{
auto [d, u] = pq.top();
pq.pop();
if (d > dis[u]) continue; // 旧数据跳过
for (auto [v, w] : g[u])
if (dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
pq.push({dis[v], v});
}
}
}
</syntaxhighlight>

时间复杂度：<math>O(m\log m)</math>。

== Bellman-Ford 与 SPFA ==

可处理'''负权边'''，SPFA 是 Bellman-Ford 的队列优化版。

<syntaxhighlight lang="cpp">
// SPFA
int dis[MAXN], cnt[MAXN];
bool inq[MAXN];

bool spfa(int s)
{
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
queue<int> q;
q.push(s);
inq[s] = true;

while (!q.empty())
{
int u = q.front();
q.pop();
inq[u] = false;
for (auto [v, w] : g[u])
if (dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return false; // 存在负环
if (!inq[v])
{
q.push(v);
inq[v] = true;
}
}
}
return true; // 无负环
}
</syntaxhighlight>

[[Category:图论]]
[[Category:三三文档]]

11-图论/03-最短路 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档