最短路径算法区分c++
时间: 2023-11-03 19:57:43 浏览: 43
最短路径算法中,Floyd算法使用一个三维数组 ans[k][i][j],表示可以经过的中间结点序号小于等于k 时,顶点 i 到顶点 j 的最小代价。具体来说,Floyd算法通过比较顶点i到顶点j的直接路径和通过顶点k的路径之和,来更新最小代价。在算法的每一轮迭代中,通过逐渐增加中间结点的数量,来不断优化最短路径。最后一轮迭代完成后,得到的结果即为所有路径的最短值。
相关问题
dijkstra最短路径算法c++实现
好的,以下是Dijkstra最短路径算法的C++实现。假设我们有一个无向图,节点编号为0到n-1,图的邻接矩阵为graph。
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h> // for INT_MAX
using namespace std;
// Dijkstra最短路径算法
void Dijkstra(vector<vector<int>>& graph, int start)
{
int n = graph.size();
// 存储每个节点的最短路径
vector<int> dist(n, INT_MAX);
// 起点到起点的距离为0
dist[start] = 0;
// 存储已经处理过的节点
vector<bool> visited(n, false);
// 优先队列,按照距离排序
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 把起点加入队列
pq.push({0, start});
while (!pq.empty())
{
// 取出队首节点
int u = pq.top().second;
pq.pop();
// 如果已经处理过,跳过
if (visited[u]) continue;
// 标记为已处理
visited[u] = true;
// 更新相邻节点的最短路径
for (int v = 0; v < n; ++v)
{
// 如果节点v未处理过,且u到v有边
if (!visited[v] && graph[u][v])
{
// 如果通过u到v的距离更短
if (dist[u] + graph[u][v] < dist[v])
{
// 更新最短路径
dist[v] = dist[u] + graph[u][v];
// 把节点加入队列
pq.push({dist[v], v});
}
}
}
}
// 输出最短路径
for (int i = 0; i < n; ++i)
{
cout << "Start " << start << " to " << i << " : " << dist[i] << endl;
}
}
int main()
{
// 无向图的邻接矩阵
vector<vector<int>> graph = {
{0, 1, 4, 0, 0},
{1, 0, 2, 7, 0},
{4, 2, 0, 3, 5},
{0, 7, 3, 0, 2},
{0, 0, 5, 2, 0}
};
Dijkstra(graph, 0);
return 0;
}
```
这个算法的时间复杂度为O(nlogn),其中n为节点数。
单元最短路径算法C++
单元最短路径算法有多种实现方式,其中比较常用的是Dijkstra算法和Bellman-Ford算法。下面给出它们的C++实现。
1. Dijkstra算法
Dijkstra算法用于求解从起点到终点的最短路径,要求边的权值非负。算法的基本思想是从起点开始,每次找到当前距离起点最近的一个点,然后用该点更新其它点的距离,直到到达终点或者所有点都被访问过。
下面是Dijkstra算法的C++实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 0x3f3f3f3f;
int n, m, s, t;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.push({0, s});
while (q.size())
{
auto t = q.top();
q.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
q.push({dist[j], j});
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> s >> t;
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dijkstra();
cout << (dist[t] == INF ? -1 : dist[t]) << endl;
return 0;
}
```
2. Bellman-Ford算法
Bellman-Ford算法用于求解任意两点之间的最短路径,要求边的权值可以是负数。算法的基本思想是对所有的边进行n-1次松弛操作,其中n是图中点的个数。如果在第n-1次松弛操作后仍然存在松弛的情况,说明图中存在负环,即从起点出发可以无限循环地减小距离。
下面是Bellman-Ford算法的C++实现:
```c++
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 0x3f3f3f3f;
int n, m, s, t;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
queue<int> q;
q.push(s);
st[s] = true;
cnt[s] = 1;
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> s >> t;
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (spfa()) puts("-1");
else cout << dist[t] << endl;
return 0;
}
```