gpt4 book ai didi

c++ - 使用 Dijkstra 的最大概率路径

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:43:02 24 4
gpt4 key购买 nike

我已经使用 dijkstra 算法为双向图中的最短路径制作了这个程序。能否将此算法转化为寻找图中最长路径的程序。

#include<bits/stdc++.h>
using namespace std;

#define mp make_pair
#define ft first
#define sd second

vector< pair<long long int,long long int> > g[101000];
long long int n,m;
vector<long long int> dist;
vector <long long int> vis;

void dijkstra(long long int source,long long int l)
{
dist.clear();
long long int i,j,k;
for(i=0;i<n;i++)
{
dist.push_back(INT_MAX);
vis.push_back(0);
}
dist[source] = 0;
set< pair<long long int,long long int> > s; // pair is dist, node_number
set< pair<long long int,long long int> >::iterator it;

for(i=0;i<n;i++)
s.insert(mp(dist[i],i));

while(!s.empty())
{
it = s.begin();
pair<long long int,long long int> temp = *it;
s.erase(temp); // remove minimum val node
long long int cur = temp.sd;
long long int val = temp.ft;

if(val == INT_MAX)
return;
for(i=0;i<g[cur].size();i++)
{
long long int nb = g[cur][i].ft;
if(!vis[nb] && dist[nb] > val + g[cur][i].sd)
{
s.erase(mp(dist[nb],nb)); // erase old val
dist[nb] = val + g[cur][i].sd;
s.insert(mp(dist[nb],nb));
}
}
}
for(int i=0;i<n;i++)
{
cout<<dist[i]<<" ";
}
cout<<endl;

}
int main()
{
long long int i,j,k;

dist.clear();
vis.clear();

long long int x,y,z;
cin>>n>>m;
for(i=0;i<m;i++)
g[i].clear();

for(i=0;i<m;i++)
{
cin>>x>>y>>z;
x--; y--;

g[x].push_back(mp(y,z));
g[y].push_back(mp(x,z));
}
dijkstra(0,n-1);

return 0;
}

基本上我有的是概率而不是路径成本,所以我想要的是概率最大的路径。我怎样才能实现这一目标。

最佳答案

(Offtopic - 使用 #include <bits/stdc++.h> 是一种不可移植的 hack。)

Basically i have is probabilities instead of path cost, so i want is the path with max probability. How can i go about achieving this.

假设从 s 开始,您想找到每个 v 的最大概率路径。如果具有概率 Πipi 的路径在这些路径中最大,则 -∑i log(pi) 最小。请注意,这对应于每个边权重为正的 log(1/pi) 的图,因此您可以应用 Dijkstra(不会有负权重周期)。

关于c++ - 使用 Dijkstra 的最大概率路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40316698/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com