สมมติเรามีกราฟที่มีโหนดและเส้นเชื่อม แต่ละเส้นมีน้ำหนักเป็น Binary คือ 0 หรือ 1 กำหนด Source Vertex เราต้องหา Shortest Path จาก Source ไปยังโหนดอื่นๆ สมมติกราฟแบบด้านล่าง
ใน BFS ปกติ น้ำหนักเส้นเท่ากันทุกเส้น แต่ที่นี่มี 0 และ 1 ทุกขั้นตอนเราตรวจสอบเงื่อนไขระยะทางที่เหมาะสม ใช้ Double-ended Queue (Deque) เก็บโหนด ถ้าน้ำหนัก 0 ใส่หน้า (Front) ถ้า 1 ใส่ท้าย (Back) ดูอัลกอริทึมเพื่อเข้าใจดีขึ้น
อัลกอริทึม
binaryBFS(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 edges[V];
void binaryBFS(int src) {
int dist[V];
for (int i=0; i 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 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 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ผลลัพธ์
1 1 1 1 1 2 0 1
