알 수없는 테스트 케이스에서 실패한 Bellman Ford 알고리즘

Question

이전 코스 중 하나에 대해 설정 한 문제에 대해 작업하고 있습니다. 노드에 도달 할 수 있지만 경우 노드 (*로 출력)

는 s에서 도달 할 수없는 경우

1. : 나는 소스 s에서, 나는 다음을 찾을 수 있다고 벨만 포드 알고리즘은 구현 하죠 음의주기 A A 부분 및 따라서 더 짧은 경로가 없다 (-로서 출력) 그렇지
2. , I는 FOLLO를 작성한

노드에 s 출력 최단 알려지지 않은 테스트 케이스에서 실패하는 윙 코드. 누군가 나를 디버깅 할 수 있습니까?

void relax_edges(vector <vector<int>> &adj, 
       vector <vector<int>> &cost, 
       vector<long long> &dis) 
    { 
    /*Takes input as adjacency list and relax all possible edges 
    */ 

    for (int i = 0; i < adj.size(); i++) { 
    for (int j = 0; j < adj[i].size(); j++) { 
     if (dis[i] < std::numeric_limits < long long > ::max() 
      && dis[adj[i][j]] > dis[i] + cost[i][j]){ 
     //std::cout<< adj[i][j]<<" "<<i<<"\n"; 
     dis[adj[i][j]] = dis[i] + cost[i][j]; 
     } 
    } 
    } 
} 

void bfs(vector<vector<int> > &adj, vector<int>& shortest, int s){ 
    vector<int> seen (adj.size(), 0); 
    //seen[s] = 1; 
    queue<int> q; 
    q.push(s); 
    int t; 
    while(!q.empty()){ 
     t = q.front(); 
     q.pop(); 
     if (seen[t] == 3) 
      break; 
     seen[t]+=1; 
     for(int i=0;i<adj[t].size();i++){ 
      q.push(adj[t][i]); 
     } 
    } 

    for(int i=0;i<seen.size();i++) 
     if(seen[i]>=1) 
      shortest[i] = 0; 
} 

void shortest_paths(vector <vector<int>> &adj, 
        vector <vector<int>> &cost, 
        int s, 
        vector<long long> &dis, 
        vector<int> &reachable, 
        vector<int> &shortest) { 

    dis[s] = 0;// distance of s is 0 from s  
    int result; 
    for (int i = 0; i < adj.size() - 1; i++) { //Running Bellman Ford |V-1| times 
    relax_edges(adj, cost, dis); 
    } 
    vector<long long> distance2(dis.size(), 0); 
    for (int i = 0; i < distance2.size(); i++) 
    distance2[i] = dis[i]; 

    relax_edges(adj, cost, distance2); // Running it |V|th time to identify negative cycle nodes 
    relax_edges(adj, cost, distance2); //Running it |V+1|th time to identify the first node of the negative cycle. 


    for(int i=0;i<distance2.size();i++){ 
    //std::cout<<distance2[i]<<" "<<dis[i]<<"\n"; 
    if(distance2[i]!=dis[i]){ 
     bfs(adj, shortest, i); 
     shortest[i] = 0; 
    } 
    if (dis[i] < std::numeric_limits<long long>::max()) 
     reachable[i] = 1;  
    } 
} 

문제는 어떤 테스트 케이스가 실패했는지 식별 할 수 없다는 것입니다.

Answer 1

문제를 잘못 해석했다고 생각합니다. 내 의견으로는 2.되어야한다 :

를 노드가 연결할 수 있지만에서 떨어져 의 도달 부정적인 사이클이므로, 더 짧은 경로가없는 경우 (같은 출력 -)

분명히 부정적인 주기로 돌아가서 임의의 수의 사이클을 만들고 목적지까지 달릴 수 있습니다.

두 번째 문제는 의 반복이 음수 사이클에서 모든 노드를 찾지 못하는 것입니다. relax_edges입니다. 문제를 해결하기

한 가지 방법은 다음과 같습니다

1. 실행 relax_edge의 relax_edges
2. 중 하나를 실행 반복 이상 |V|-1 반복 부정적인 사이클에 대한 몇 가지 노드를 찾을 수 있습니다. 모든 음수주기마다 최소한 하나의 노드를 감지 할 수 있습니다.
3. 이러한 감지 된 노드에서 bfs 또는 dfs를 실행하여 부정 사이클에서 도달 할 수있는 모든 노드를 찾습니다 (이들 노드에 대해 잘 정의 된 최단 경로 없음).

편집 : 다음의 예와, relax_edges2*|V|에 대한 시간을 실행하는 @ Ardavel의 제안은 작동하지 않습니다 :

relax_edges 8 회를 실행 한 후, 하나의 생각, 1에서 4까지의 최단 경로가 직접 가장자리 인 1->4을 차지한다는 것입니다. 그러나 부정적인주기 (2 < -> 3)에서 2,000 번 이상을 실행하고 4 번 출구로 나가는 것보다 2를 실행할 수 있기 때문에 최단 경로가 아닙니다.

2000 시간 이상 relax_edge을 실행해야합니다!

이것은 부정적인주기에서 첫 번째 노드를 발견 한 후 원하는대로 bfs/dfs/other 알고리즘을 수행해야하는 이유입니다.

Answer 2

구현에 실패한 예를 제공 할 수 있습니다. 나는 또한 문제에 대한 해결책을 설명 할 것이다.

relax_edges|V| - 1 번 실행 후 음수주기가 없다고 가정 할 때 원본에서 유효한 최단 경로를 모두 찾을 수 있습니다. |V| 시간 동안 휴식을 취한 후 근원으로부터 도달 할 수있는 부정적인주기가 있는지 확인할 수 있습니다 (최단 거리가 감소한 경우). 그러나 이것은 모든 노드에 대해 도달 가능한 음수 사이클에 있는지 여부를 말하는 것만으로는 충분하지 않습니다.

아래 예제를 참조하십시오 (무한대의 경우 INF 상태). 당신이 볼 수 있듯이

의 |V| 번째 휴식 후 우리는 소스 (노드 3)에서 도달 부정적인주기가 있다고 말할 수있다. 소스로부터의 최단 경로가 방금 감소한 노드 (2 및 3)가 있기 때문에이를 알고 있습니다. 그러나 두 개의 추가 완화 후 (구현 에서처럼) 노드 0이 음수주기에 있다는 것을 여전히 알 수 없습니다. 소스로부터의 최단 거리는 |V| - 1 휴식 시간과 동일합니다.

다음 사항에 유의하십시오. 노드가 어떤 부정적인주기에 놓이는 경우, 또한 길이가 음수 인주기 인 |V|에 놓입니다. 이것은 단순한 그래프와 멀티 그래프에서 마찬가지입니다. 따라서 알고리즘의 두 번째 부분에서 relax_edges을 한두 번 실행하는 대신 |V| 번 실행해야합니다. 이렇게하면 각 노드에 대해 노드가 포함 된 전체 음수 사이클을 탐색 할 가능성이 있는지 확인할 수 있습니다. 이 |V| 휴식 후 추가로 가장 가까운 거리와 첫 번째 |V| - 1 휴식 시간을 비교할 수 있습니다. 노드에 대한 최단 거리가 더 낮 으면 소스에서 도달 할 수있는 음수주기에 있는지 확인할 수 있습니다.

물론 제공된 솔루션은 O (| V | * | E |) 인 시간 복잡도를 증가시키지 않습니다. 단점은 더 높은 상수입니다.

문제가있는 문장에서 가장 짧은 경로가 있으면 반환해야한다고 언급했습니다. 그러나, 당신이 제공 한 코드에서 관련 부분을 볼 수 없습니다. 이것이 누락 된 것이라면 휴식 중 거리를 업데이트 할 때마다 노드의 선행자를 기억하면됩니다. 선행 작업을 업데이트하는 좋은 간단한 예제는 Wikipedia에 있습니다. 최단 경로가있는 각 노드에 대한 선행 작업이있는 경우 소스에 도달 할 때까지 경로를 거슬러 올라갈 수 있습니다.

는 편집 :

@ead 내가 너무 말 그대로 내가 내 대답을 개선하고있어 "2"요구 사항을 찍은 것으로 나타났다. 제가 제시 한 알고리즘은 소스에서 도달 할 수있는 부정적인 사이클의 일부인지 여부를 각 노드에 알릴 수 있습니다. 그러나 자체적으로 부정적인주기의 일부가 아닌 노드가있을 수 있지만 소스에서 도달 할 수있는 부정적인주기에서이 노드에 도달 할 수 있습니다. 따라서 어떤 노드에 대한 최단 경로가 존재한다고 말하면 소스에서 도달 할 수있는 부정적인주기에서 도달 할 수 없는지 확인해야합니다.

@ead가 제시 한 매우 합리적인 해결책은 |V|- 완화 중 네거티브 사이클의 일부로 감지되는 모든 노드에서 그래프 검색 (DFS 또는 BFS)을 실행하는 것입니다. 예를 들어 shortest[i] = 0을 수행 할 때마다 i 노드를 큐에 추가합니다. 그런 다음 큐에 이미있는 여러 개의 시작 노드가있는 단일 BFS를 실행할 수 있습니다. 이 BFS 동안 방문한 각 노드는 소스에서 도달 할 수있는 부정적인주기의 일부이므로 최단 경로가 없습니다.

편집 2 :

BFS와 접근 방식은 일반적으로 정확하지만 구현이 잘못 생각합니다. 나는 seen[t] == 3 일지 검사 점을 볼 수 없다. 각 노드에 대해 그래프 검색 중에 방문했는지 여부 만 기억하면됩니다. 마찬가지로 큐에 푸시 될 때마다 각 노드를 seen으로 표시 할 수 있습니다.

void bfs(vector<vector<int>>& adj, vector<int>& shortest, int s) { 
    vector<int> seen(adj.size(), 0); 

    queue<int> q; 
    q.push(s); 
    seen[s] = 1; 

    while (!q.empty()) { 
     int t = q.front(); 
     q.pop(); 

     for (int i = 0; i < adj[t].size(); ++i) { 
      if (!seen[adj[t][i]]) { 
       q.push(adj[t][i]); 
       seen[adj[t][i]] = 1; 
      } 
     } 
    } 

    for (int i = 0; i < seen.size(); ++i) { 
     if (seen[i] > 0) {   
      shortest[i] = 0; 
     } 
    } 
} 

I는 shortest_paths 함수 내부 큐를 생성하고 그것을 distance2[i] != dis[i] 만족 각 노드 추진 추천 것이다 : 여기 BFS 고정 된 버전이다. 그런 다음 초기화 된 대기열을 사용하여 BFS를 한 번만 실행해야합니다.