Hello Codeforces. I have just recently joined a contest at my school. In that contest, there was a problem requiring counting the number of shortest paths from a vertex s to every other vertex in a directed weighted graph. I have implemented my idea and tested it a bit so I had a strong belief that my code was correct. In the end, it turned out that the code was wrong. The contest gave me only one submission for each problem so I didn't have a chance to fix it during the contest. I have tried to find my mistakes in the code at home but I found nothing. Here is the code similar to what I submitted during the contest.↵
↵
<spoiler summary="The code">↵
~~~~~↵
void Dijkstra (int s)↵
{↵
// dist[i] is the minimum distance from s to i↵
// num[i] is the number of shortest paths from s to i↵
for (int i=1; i<=n; i++)↵
{↵
dist[i]=inf;↵
num[i]=0;↵
}↵
dist[s]=0;↵
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;↵
pq.push({0,s});↵
num[s]=1;↵
while (!pq.empty())↵
{↵
pair<int,int> tmp=pq.top();↵
pq.pop();↵
int u=tmp.second;↵
for (auto g:adj[u])↵
{↵
// v is the adjacent vertex with u↵
// w is the weight of the edge u-v↵
int v=g.second;↵
int w=g.first;↵
if (dist[v]==dist[u]+w)↵
{↵
num[v]+=num[u];↵
}↵
if (dist[v]>dist[u]+w)↵
{↵
dist[v]=dist[u]+w;↵
num[v]=num[u];↵
pq.push({dist[v],v});↵
}↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Can anyone help me point out the mistake in the algorithm or maybe this was not the incorrect part in my initial code? I would be so grateful if you can provide a link to another problem that also requires counting the number of shortest paths so that I can test the code by myself. Thanks for reading and have a good day.
↵
<spoiler summary="The code">↵
~~~~~↵
void Dijkstra (int s)↵
{↵
// dist[i] is the minimum distance from s to i↵
// num[i] is the number of shortest paths from s to i↵
for (int i=1; i<=n; i++)↵
{↵
dist[i]=inf;↵
num[i]=0;↵
}↵
dist[s]=0;↵
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;↵
pq.push({0,s});↵
num[s]=1;↵
while (!pq.empty())↵
{↵
pair<int,int> tmp=pq.top();↵
pq.pop();↵
int u=tmp.second;↵
for (auto g:adj[u])↵
{↵
// v is the adjacent vertex with u↵
// w is the weight of the edge u-v↵
int v=g.second;↵
int w=g.first;↵
if (dist[v]==dist[u]+w)↵
{↵
num[v]+=num[u];↵
}↵
if (dist[v]>dist[u]+w)↵
{↵
dist[v]=dist[u]+w;↵
num[v]=num[u];↵
pq.push({dist[v],v});↵
}↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
Can anyone help me point out the mistake in the algorithm or maybe this was not the incorrect part in my initial code? I would be so grateful if you can provide a link to another problem that also requires counting the number of shortest paths so that I can test the code by myself. Thanks for reading and have a good day.
