Блог пользователя Hd7

Find all vertices in negative cycle or reachable from it in Directed Graph.
Автор Hd7, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится 
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;
→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить