0-1 C 프로그램에서 BFS(이진 가중치 그래프의 최단 경로)?

일부 노드와 연결된 간선이 있는 그래프가 있다고 가정합니다. 각 간선에는 이진 가중치가 있습니다. 따라서 가중치는 0 또는 1이 됩니다. 소스 정점이 제공됩니다. 소스에서 다른 정점까지의 최단 경로를 찾아야 합니다. 그래프가 아래와 같다고 가정 -

일반 BFS 알고리즘에서 모든 간선 가중치는 동일합니다. 여기에서 일부는 0이고 일부는 1입니다. 각 단계에서 최적의 거리 조건을 확인합니다. 여기서 우리는 노드를 저장하기 위해 이중 종료 큐를 사용할 것입니다. 그래서 우리는 가장자리 무게를 확인할 것입니다. 0이면 앞쪽으로 밀고, 아니면 뒤쪽으로 밀어 넣습니다. 더 나은 아이디어를 얻기 위해 알고리즘을 확인해 보겠습니다.

알고리즘

바이너리BFS(src) -

begin
   define dist array to store source to vertex i into dist[i]. Initially fill with infinity
   dist[src] := 0
   insert src into queue Q.
   v := first element from Q, and delete it from queue
   while Q is not empty, do
      for all connected edge e of v, do
         if the weight of v to next of i > dist[v] + weight of v to i weight, then update the weight
            if the weight is 0, then store to front, otherwise back
         end if
      done
   done
   print all distance from dist array
end

예시

#include<iostream>
#include<vector>
#include<deque>
#define V 8
using namespace std;
struct node {
   int next, weight;
};
vector <node> edges[V];
void binaryBFS(int src) {
   int dist[V];
   for (int i=0; i<V; i++) //initially set as infinity
      dist[i] = INT_MAX;
   deque <int> Q;
   dist[src] = 0; //distance from source to source is 0
   Q.push_back(src);
   while (!Q.empty()) {
      int v = Q.front(); //delete first vertex, and store to v
      Q.pop_front();
      for (int i=0; i<edges[v].size(); i++) {
         //check optimal distance
         if (dist[edges[v][i].next] > dist[v] + edges[v][i].weight) {
            dist[edges[v][i].next] = dist[v] + edges[v][i].weight;
            if (edges[v][i].weight == 0) //0 weight edge is stored at front, otherwise at back
               Q.push_front(edges[v][i].next);
            else
               Q.push_back(edges[v][i].next);
         }
      }
   }
   for (int i=0; i<V; i++)
      cout << dist[i] << " ";
}
void addEdge(int u, int v, int wt) {
   edges[u].push_back({v, wt});
   edges[v].push_back({u, wt});
}
int main() {
   addEdge(0, 1, 0);
   addEdge(0, 3, 1);
   addEdge(0, 4, 0);
   addEdge(1, 2, 1);
   addEdge(1, 7, 0);
   addEdge(2, 5, 1);
   addEdge(2, 7, 0);
   addEdge(3, 4, 0);
   addEdge(3, 6, 1);
   addEdge(4, 6, 1);
   addEdge(5, 7, 1);
   addEdge(6, 7, 1);
   int src = 6;
   binaryBFS(src);
}

출력

1 1 1 1 1 2 0 1