Sep 23, 2024 · Oct 24, 2024 · Oct 24, 2024
diff --git a/src/graph/01_bfs.md b/src/graph/01_bfs.md
 We can develop the algorithm by closely studying Dijkstra's algorithm and thinking about the consequences that our special graph implies.
 The general form of Dijkstra's algorithm is (here a `set` is used for the priority queue):

 ```cpp
 d.assign(n, INF);
 d[s] = 0;
 set<pair<int, int>> q;
 q.insert({0, s});
 while (!q.empty()) {
    int v = q.begin()->second;
    q.erase(q.begin());

    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;

        if (d[v] + w < d[u]) {
            q.erase({d[u], u});
            d[u] = d[v] + w;
            q.insert({d[u], u});
 === "C++"
    ```cpp
    d.assign(n, INF);
    d[s] = 0;
    set<pair<int, int>> q;
    q.insert({0, s});
    while (!q.empty()) {
        int v = q.begin()->second;
        q.erase(q.begin());

        for (auto edge : adj[v]) {
            int u = edge.first;
            int w = edge.second;

            if (d[v] + w < d[u]) {
                q.erase({d[u], u});
                d[u] = d[v] + w;
                q.insert({d[u], u});
            }
        }
    }
 }
 ```
    ```
 === "Python"
    ```py
    from heapq import heappop, heappush


    d = [float("inf")] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dv, v = heappop(q)
        if dv == d[v]:
            for u, w in adj[v]:
                if d[v] + w < d[u]:
                    d[u] = d[v] + w
                    heappush(q, (d[u], u))
    ```

 We can notice that the difference between the distances between the source `s` and two other vertices in the queue differs by at most one.
 Especially, we know that $d[v] \le d[u] \le d[v] + 1$ for each $u \in Q$.
 We can simply use a normal queue, and append new vertices at the beginning if the corresponding edge has weight $0$, i.e. if $d[u] = d[v]$, or at the end if the edge has weight $1$, i.e. if $d[u] = d[v] + 1$.
 This way the queue still remains sorted at all time.

 ```cpp
 vector<int> d(n, INF);
 d[s] = 0;
 deque<int> q;
 q.push_front(s);
 while (!q.empty()) {
    int v = q.front();
    q.pop_front();
    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;
        if (d[v] + w < d[u]) {
            d[u] = d[v] + w;
            if (w == 1)
                q.push_back(u);
            else
                q.push_front(u);
 === "C++"
    ```cpp
    vector<int> d(n, INF);
    d[s] = 0;
    deque<int> q;
    q.push_front(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        for (auto edge : adj[v]) {
            int u = edge.first;
            int w = edge.second;
            if (d[v] + w < d[u]) {
                d[u] = d[v] + w;
                if (w == 1)
                    q.push_back(u);
                else
                    q.push_front(u);
            }
        }
    }
 }
 ```
    ```
 === "Python"
    ```py
    d = [float("inf")] * n
    d[s] = 0
    q = deque([s])
    while q:
        v = q.popleft()
        for u, w in adj[v]:
            if d[v] + w < d[u]:
                d[u] = d[v] + w
                if w == 1:
                    q.append(u)
                else:
                    q.appendleft(u)
    ```

 ## Dial's algorithm