Hd7's blog

By Hd7, history, 19 months ago, In English

I have solved UVa-10499 Traffic.
The problem ask to find out all shortest path from vertex 1, if vertices are affected by negative cycle, it means the shortest path become undefined and we print ?. I solved it with Bellman-Ford algorithm and it passed but I feel my approach is incorrect and I found a counter-example.

My approach: In the nth-relaxation, if vertices are shorten, I assign shortest path to them equal $$$-\infty$$$.

for(auto e:edges){
    int u, v, w; tie(u, v, w) = e;
    if (d[u]+w < d[v]) {
        d[v] = -INF;
    }
}

My fully solution: https://ideone.com/TfuoGz
For example, I have this graph and edges are stored in this order, the weight of edges represent the edges.

bb3122de4c63ab3df272.md.jpg

and in the n-th relaxation, I am just able to assign $$$-\infty$$$ to vertex 3, but vertex 2 and 4 are also affected by negative cycle.
Does the system test is weak or I understand something wrong? Could you suggest me the approach to solve this kind of problems.
Thank you!

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it
bool reachable[start][end]

void dfs(int i, int v) {
	reachable[i][v] = 1
	for (auto u : adj[v]) dfs(i, u)
}

for (i, 1, n) dfs(i, i)

bellman_ford(n - 1)

for (u, v, w : edges) if (d[u] + w < d[v]) for (i, 1, n) if (reachable[v][i]) d[i] = -INF;
  • »
    »
    19 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Did you miss it?

    void dfs(int i, int v){
        if (reachable[i][v]) return;  //this line
        reachable[i][v] = 1;
        for(auto u:adj[v]) dfs(i, u);
    }
    

    Thanks for your reply.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For anyone looking for a test case that fails the currently accepted solution: 4 1 13 11 12
4
1 2
4 2
3 4
2 3
4
1
2
3
4

Currently Accepted Output at UVa at the date of commenting:
Set #1
?
1722
1714
?

Correct Actual Output:
Set #1
?
?
?
?

I think the solution can be improved by running the Bellman-Ford for n times again after the first n-1 times. And setting the distances to -inf in n iterations after the initial n-1 iterations. I think this way the negative cycle is propagated to all the reachable vertices from the source.