#path #implementation #shortest
Вопрос:
Я пытаюсь реализовать алгоритм Джикстры для кратчайших путей из одного источника ко всем узлам для взвешенного неориентированного графа без отрицательных ребер. Код выглядит следующим образом:
typedef long long ll;
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define f first
#define s second
using namespace std;
void help(vector<vector<pll> > graph)
{
vector<ll> dist(n 1,LLONG_MAX);
dist[0]=0;
priority_queue< pll, vector <pll> , greater<pll> > pq;
pq.push(mp(0,0));//dist,v
vector<bool> visited(n 1,false);
//printArray(dist);
while(!pq.empty())
{
pii p = pq.top();
pq.pop();
if(!visited[p.s])
{
visited[p.s] = true;
dist[p.s]=p.f;
for(ll i = 0; i<graph[p.s].size(); i )
{
pq.push(mp(graph[p.s][i].s dist[p.s],graph[p.s][i].f));
}
}
// if instead of the above if block, I use the below for block, the code gives output!
// for(auto [v,d]:graph[p.s])
// {
// if(dist[v]>dist[p.s] d)
// {
// dist[v] = dist[p.s] d;
// pq.push({dist[v],v});
// }
// }
}
for(ll i = 1; i <=n; i )
{
cout << dist[i]<< " ";
}
cout << "n";
}
Реализация довольно проста, но мой код выдает неверные выходные данные, и я не могу понять причину ошибки. Замена блока if и вместо этого установка блока for дает правильный вывод, но я думаю, что оба они по сути являются одним и тем же алгоритмом. Я поддерживаю посещенный массив, и если выскочивший узел u из кучи не посещен, соответствующий ключ является кратчайшим расстоянием до u, и теперь я вставляю новые пары со key = Dist[u] wt(uv)
всеми соседями v
u
. Может ли кто-нибудь указать на алгоритмическую ошибку в моем коде?