Hd7's blog

Find all vertices in negative cycle or reachable from it in Directed Graph.
By Hd7, history, 5 years 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

Comments Comments (2)
| Write comment?
»
5 years 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;
→ Reply
  • »
    »
    5 years 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.

    → Reply