2024-11-26 21:54 哈尔滨理工大学 C++ 发布于黑龙江
关注
图的最短距离问题
1.dijkstra（无法求负边）
#include
using namespace std;
#define endl '\n'
const int N = 3e5;
int n, m, s, t;
vector > g[N];
int dis[N];
int st[N];
void dij() {
memset(dis,0x3f,sizeof(dis));
priority_queue,vector>,greater>> pq;
pq.push({0,s});
while (pq.size())
{
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (st[u])continue;
st[u] = 1;
for (auto i : g[u])
{
int v = i.first;
int w = i.second;
if (dis[v] > d + w){
dis[v] = d + w;
pq.push({dis[v],v});
}
}
}
cout << dis[t];
}
signed main()
{
std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t;
for (int i = 0;i
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dij();
return 0;
}
2.贝尔特佛特（可以求负边）
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
3.Floyd（dp思想）
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
上述算法，dijkstra时间复杂度最低，Floyd最好n的三次方，但是可以求图上连通点之间的最短距离
#include
using namespace std;
#define endl '\n'
const int N = 3e5;
int n, m, s, t;
vector
int dis[N];
int st[N];
void dij() {
memset(dis,0x3f,sizeof(dis));
priority_queue
pq.push({0,s});
while (pq.size())
{
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (st[u])continue;
st[u] = 1;
for (auto i : g[u])
{
int v = i.first;
int w = i.second;
if (dis[v] > d + w){
dis[v] = d + w;
pq.push({dis[v],v});
}
}
}
cout << dis[t];
}
signed main()
{
std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
cin >> n >> m >> s >> t;
for (int i = 0;i
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dij();
return 0;
}
2.贝尔特佛特（可以求负边）
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
3.Floyd（dp思想）
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
上述算法，dijkstra时间复杂度最低，Floyd最好n的三次方，但是可以求图上连通点之间的最短距离
全部评论
相关推荐
投递牛客等公司10个岗位 > 点赞 评论 收藏
分享