这个 dijkstra 算法实现有什么错误吗?
Is there any bug in this dijkstra algorithm implementation?
我刚刚学习了 Dijkstra 算法并解决了一些问题,我正在尝试解决这个 http://codeforces.com/problemset/problem/20/C 问题,但我在测试用例中得到错误的答案 31.I 无法理解为什么会得到错误的答案.首先,它在测试用例 31 上超出了内存限制。但是当我将 int 更改为 d[] arrray 的 long long 时,它得到了错误的答案。请告诉我为什么会得到错误答案。
我的代码:
#include <bits/stdc++.h>
using namespace std;
typedef struct data Data;
struct data{
long long int city,dis;
bool operator < (const data & p) const{
return dis > p.dis;
}
};
#define tr(niloy,it) for(auto it = niloy.rbegin(); it != niloy.rend(); it++)
void dijkstra(const vector <long long int> edge[],const vector <long long int> cost[], int source, int destination,int n,int m)
{
long long int d[n];
bool nodes[n];
vector <int> parent(n,-1);
for(int i = 0; i < n; i++){
d[i] = INT_MAX;
parent[i] = -1;
nodes[i] = false;
}
priority_queue <Data> p;
Data u,v;
u.city = 0;
u.dis = 0;
p.push(u);
d[source] = 0;
while(!p.empty()){
u = p.top();
p.pop();
long long int ucost = d[u.city];
if(u.city == destination)break;
if(nodes[u.city])continue;
nodes[u.city] = true;
//cout << edge[u.city].size() << endl;
for(int i = 0; i < edge[u.city].size(); i++){
v.dis = ucost + cost[u.city][i];
v.city = edge[u.city][i];
if(d[v.city] > v.dis){
///cout << v.city << " " << u.city << endl;
parent[v.city] = u.city;
d[v.city] = v.dis;
p.push(v);
}
}
}
vector<int> niloy;
///cout << d[destination] << endl;
if(parent[destination] != -1){
niloy.push_back(n);
while(destination != 0){
niloy.push_back(parent[destination]+1);
destination = parent[destination];
}
tr(niloy,it)cout << *it << " " ;
}else{
///cout << d[destination] << endl;
cout << -1 << endl;
}
}
int main()
{
int n,m;
cin>> n >> m;
vector <long long int> edge[n],cost[n];
int a,b,c;
for(int i = 0; i < m; i++){
cin >> a >> b >> c;
if(a == b)continue;
edge[a-1].push_back(b-1);
cost[a-1].push_back(c);
edge[b-1].push_back(a-1);
cost[b-1].push_back(c);
}
//cout << edge[0][0] << endl;
dijkstra(edge,cost,0,n-1,n,m);
return 0;
}
算法实现对我来说看起来是正确的,唯一似乎错误的是这一行:
d[i] = INT_MAX;
如果编译器使用 32 位整数,INT_MAX 将是 2^32(接近 10^9),而最佳解决方案的最大可能实际长度可能是如果您有一个线性图,例如:1 -> 2 -> 3 -> ... -> n 并且每条边的长度为 10^6,则不止于此。在这种情况下,最短路径将接近 10^11,大于 INT_MAX,这意味着 d 数组的初始值为不是真正的 "infinite" 作为 dijkstra 的算法要求。
将初始值更改为更高的数字应该可以解决此问题(10^12 应该足够了,但您也可以使用 LLONG_MAX):
d[i] = 1000000000000; // 10^12
我刚刚学习了 Dijkstra 算法并解决了一些问题,我正在尝试解决这个 http://codeforces.com/problemset/problem/20/C 问题,但我在测试用例中得到错误的答案 31.I 无法理解为什么会得到错误的答案.首先,它在测试用例 31 上超出了内存限制。但是当我将 int 更改为 d[] arrray 的 long long 时,它得到了错误的答案。请告诉我为什么会得到错误答案。
我的代码:
#include <bits/stdc++.h>
using namespace std;
typedef struct data Data;
struct data{
long long int city,dis;
bool operator < (const data & p) const{
return dis > p.dis;
}
};
#define tr(niloy,it) for(auto it = niloy.rbegin(); it != niloy.rend(); it++)
void dijkstra(const vector <long long int> edge[],const vector <long long int> cost[], int source, int destination,int n,int m)
{
long long int d[n];
bool nodes[n];
vector <int> parent(n,-1);
for(int i = 0; i < n; i++){
d[i] = INT_MAX;
parent[i] = -1;
nodes[i] = false;
}
priority_queue <Data> p;
Data u,v;
u.city = 0;
u.dis = 0;
p.push(u);
d[source] = 0;
while(!p.empty()){
u = p.top();
p.pop();
long long int ucost = d[u.city];
if(u.city == destination)break;
if(nodes[u.city])continue;
nodes[u.city] = true;
//cout << edge[u.city].size() << endl;
for(int i = 0; i < edge[u.city].size(); i++){
v.dis = ucost + cost[u.city][i];
v.city = edge[u.city][i];
if(d[v.city] > v.dis){
///cout << v.city << " " << u.city << endl;
parent[v.city] = u.city;
d[v.city] = v.dis;
p.push(v);
}
}
}
vector<int> niloy;
///cout << d[destination] << endl;
if(parent[destination] != -1){
niloy.push_back(n);
while(destination != 0){
niloy.push_back(parent[destination]+1);
destination = parent[destination];
}
tr(niloy,it)cout << *it << " " ;
}else{
///cout << d[destination] << endl;
cout << -1 << endl;
}
}
int main()
{
int n,m;
cin>> n >> m;
vector <long long int> edge[n],cost[n];
int a,b,c;
for(int i = 0; i < m; i++){
cin >> a >> b >> c;
if(a == b)continue;
edge[a-1].push_back(b-1);
cost[a-1].push_back(c);
edge[b-1].push_back(a-1);
cost[b-1].push_back(c);
}
//cout << edge[0][0] << endl;
dijkstra(edge,cost,0,n-1,n,m);
return 0;
}
算法实现对我来说看起来是正确的,唯一似乎错误的是这一行:
d[i] = INT_MAX;
如果编译器使用 32 位整数,INT_MAX 将是 2^32(接近 10^9),而最佳解决方案的最大可能实际长度可能是如果您有一个线性图,例如:1 -> 2 -> 3 -> ... -> n 并且每条边的长度为 10^6,则不止于此。在这种情况下,最短路径将接近 10^11,大于 INT_MAX,这意味着 d 数组的初始值为不是真正的 "infinite" 作为 dijkstra 的算法要求。
将初始值更改为更高的数字应该可以解决此问题(10^12 应该足够了,但您也可以使用 LLONG_MAX):
d[i] = 1000000000000; // 10^12