rust_algorithms/graph/

shortest_path.rs

//! Eng qisqa yo'l algoritmlari: BFS, Dijkstra, Bellman-Ford, Floyd-Warshall.

use super::Graph;
use std::cmp::Reverse;
use std::collections::{BinaryHeap, VecDeque};

/// Og'irliksiz grafda eng qisqa yo'l — oddiy BFS.
///
/// Og'irliklar teng bo'lsa, Dijkstra ortiqcha: BFS **O(V+E)** da javob beradi.
///
/// Qaytadi: `start` dan `goal` gacha bo'lgan yo'l (tugunlar ro'yxati) yoki `None`.
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, bfs_shortest_path};
///
/// let mut g = Graph::new_undirected(6);
/// for (a, b) in [(0, 1), (1, 2), (2, 5), (0, 3), (3, 4), (4, 5)] {
///     g.add_unweighted_edge(a, b);
/// }
/// let yol = bfs_shortest_path(&g, 0, 5).unwrap();
/// assert_eq!(yol.len(), 4); // 0 → 1 → 2 → 5 (yoki 0 → 3 → 4 → 5)
/// assert_eq!(yol[0], 0);
/// assert_eq!(*yol.last().unwrap(), 5);
/// ```
pub fn bfs_shortest_path(g: &Graph, start: usize, goal: usize) -> Option<Vec<usize>> {
    let n = g.node_count();
    let mut ota: Vec<Option<usize>> = vec![None; n];
    let mut korilgan = vec![false; n];
    korilgan[start] = true;

    let mut navbat = VecDeque::from([start]);
    while let Some(u) = navbat.pop_front() {
        if u == goal {
            return Some(yolni_tikla(&ota, start, goal));
        }
        for e in g.neighbors(u) {
            if !korilgan[e.to] {
                korilgan[e.to] = true;
                ota[e.to] = Some(u);
                navbat.push_back(e.to);
            }
        }
    }
    if start == goal {
        Some(vec![start])
    } else {
        None
    }
}

/// **Dijkstra** — musbat og'irlikli grafda bitta manbadan barcha tugunlargacha
/// eng qisqa masofalar.
///
/// **G'oya (ochko'zlik):** har qadamda "hali tekshirilmagan, lekin hozircha eng yaqin"
/// tugunni olamiz va uning qo'shnilariga masofani yangilaymiz (relaxation).
/// Musbat og'irliklarda bir marta olingan tugunning masofasi boshqa yaxshilanmaydi.
///
/// - **Time:** O((V + E) log V) — min-heap bilan. **Space:** O(V).
/// - **Cheklov:** og'irliklar **manfiy bo'lmasligi** kerak
///   (manfiy bo'lsa → [`bellman_ford`]).
///
/// Qaytadi: har bir tugun uchun masofa; yetib bo'lmasa `None`.
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, dijkstra};
///
/// //  0 --4-- 1 --1-- 3
/// //   \      |
/// //    1     2
/// //     \    |
/// //      --- 2
/// let mut g = Graph::new_undirected(4);
/// g.add_edge(0, 1, 4);
/// g.add_edge(0, 2, 1);
/// g.add_edge(2, 1, 2);
/// g.add_edge(1, 3, 1);
///
/// let d = dijkstra(&g, 0);
/// assert_eq!(d[0], Some(0));
/// assert_eq!(d[2], Some(1));
/// assert_eq!(d[1], Some(3)); // 0→2→1 = 1+2 = 3, to'g'ridan-to'g'ri 4 dan arzon
/// assert_eq!(d[3], Some(4));
/// ```
pub fn dijkstra(g: &Graph, start: usize) -> Vec<Option<i64>> {
    let (masofa, _) = dijkstra_with_parents(g, start);
    masofa
}

/// Dijkstra + yo'lni tiklash: `start` dan `goal` gacha `(narx, yo'l)`.
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, dijkstra_path};
///
/// let mut g = Graph::new_undirected(4);
/// g.add_edge(0, 1, 4);
/// g.add_edge(0, 2, 1);
/// g.add_edge(2, 1, 2);
/// g.add_edge(1, 3, 1);
///
/// let (narx, yol) = dijkstra_path(&g, 0, 3).unwrap();
/// assert_eq!(narx, 4);
/// assert_eq!(yol, vec![0, 2, 1, 3]);
/// ```
pub fn dijkstra_path(g: &Graph, start: usize, goal: usize) -> Option<(i64, Vec<usize>)> {
    let (masofa, ota) = dijkstra_with_parents(g, start);
    let narx = masofa[goal]?;
    Some((narx, yolni_tikla(&ota, start, goal)))
}

fn dijkstra_with_parents(g: &Graph, start: usize) -> (Vec<Option<i64>>, Vec<Option<usize>>) {
    let n = g.node_count();
    let mut masofa: Vec<Option<i64>> = vec![None; n];
    let mut ota: Vec<Option<usize>> = vec![None; n];

    // Rustning BinaryHeap — max-heap. Reverse bilan uni min-heapga aylantiramiz.
    let mut heap = BinaryHeap::new();
    masofa[start] = Some(0);
    heap.push(Reverse((0i64, start)));

    while let Some(Reverse((d, u))) = heap.pop() {
        // Eskirgan yozuv (bir tugun heapga bir necha marta tushishi mumkin)
        if masofa[u].is_some_and(|m| d > m) {
            continue;
        }
        for e in g.neighbors(u) {
            debug_assert!(e.weight >= 0, "Dijkstra manfiy og'irlik bilan ishlamaydi");
            let yangi = d + e.weight;
            if masofa[e.to].is_none_or(|m| yangi < m) {
                masofa[e.to] = Some(yangi);
                ota[e.to] = Some(u);
                heap.push(Reverse((yangi, e.to)));
            }
        }
    }
    (masofa, ota)
}

/// **Bellman-Ford** — manfiy og'irliklar bilan ham ishlaydi va manfiy siklni aniqlaydi.
///
/// **G'oya:** har bir qirrani `V-1` marta "bo'shatamiz" (relax). Nima uchun `V-1`?
/// Chunki siklsiz eng qisqa yo'lda ko'pi bilan `V-1` ta qirra bo'ladi.
/// `V` -iteratsiyada ham yaxshilanish bo'lsa — demak **manfiy sikl** bor.
///
/// - **Time:** O(V · E), **Space:** O(V).
/// - Manfiy sikl topilsa → `None`.
///
/// **Real qo'llanilishi:** valyuta arbitraji (manfiy sikl = foyda), tarmoq
/// marshrutlash (RIP protokoli).
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, bellman_ford};
///
/// let mut g = Graph::new_directed(4);
/// g.add_edge(0, 1, 4);
/// g.add_edge(0, 2, 5);
/// g.add_edge(1, 3, 5);
/// g.add_edge(2, 1, -3); // manfiy qirra — Dijkstra bu yerda xato qiladi
///
/// let d = bellman_ford(&g, 0).unwrap();
/// assert_eq!(d[1], Some(2)); // 0→2→1 = 5 + (−3) = 2
/// assert_eq!(d[3], Some(7));
/// ```
pub fn bellman_ford(g: &Graph, start: usize) -> Option<Vec<Option<i64>>> {
    let n = g.node_count();
    let mut masofa: Vec<Option<i64>> = vec![None; n];
    masofa[start] = Some(0);

    let qirralar: Vec<(usize, usize, i64)> = (0..n)
        .flat_map(|u| g.neighbors(u).iter().map(move |e| (u, e.to, e.weight)))
        .collect();

    for _ in 0..n.saturating_sub(1) {
        let mut ozgardi = false;
        for &(u, v, w) in &qirralar {
            if let Some(du) = masofa[u] {
                if masofa[v].is_none_or(|dv| du + w < dv) {
                    masofa[v] = Some(du + w);
                    ozgardi = true;
                }
            }
        }
        if !ozgardi {
            break; // erta to'xtash: hech narsa yaxshilanmadi
        }
    }

    // Manfiy sikl tekshiruvi
    for &(u, v, w) in &qirralar {
        if let Some(du) = masofa[u] {
            if masofa[v].is_none_or(|dv| du + w < dv) {
                return None;
            }
        }
    }
    Some(masofa)
}

/// **Floyd-Warshall** — **barcha juftliklar** orasidagi eng qisqa masofalar.
///
/// **G'oya (dinamik dasturlash):** `k` ni 0 dan V-1 gacha yurgizib, "faqat
/// `0..=k` tugunlaridan o'tishga ruxsat berilsa, i dan j gacha eng qisqa masofa
/// qancha?" degan savolga javob beramiz. Uch qatorli tsikl — algoritmning butun mohiyati:
///
/// ```text
/// d[i][j] = min(d[i][j], d[i][k] + d[k][j])
/// ```
///
/// - **Time:** O(V³), **Space:** O(V²).
/// - Kichik graflarda (V ≤ 500) juda qulay; manfiy qirralarga ruxsat (manfiy siklsiz).
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, floyd_warshall};
///
/// let mut g = Graph::new_directed(3);
/// g.add_edge(0, 1, 3);
/// g.add_edge(1, 2, 4);
/// g.add_edge(0, 2, 10);
///
/// let d = floyd_warshall(&g);
/// assert_eq!(d[0][2], Some(7)); // 0→1→2 = 7 < 10
/// assert_eq!(d[2][0], None);    // teskari yo'l yo'q
/// assert_eq!(d[1][1], Some(0));
/// ```
pub fn floyd_warshall(g: &Graph) -> Vec<Vec<Option<i64>>> {
    let n = g.node_count();
    let mut d: Vec<Vec<Option<i64>>> = vec![vec![None; n]; n];

    for (i, qator) in d.iter_mut().enumerate() {
        qator[i] = Some(0);
    }
    for u in 0..n {
        for e in g.neighbors(u) {
            let hozirgi = d[u][e.to];
            if hozirgi.is_none_or(|x| e.weight < x) {
                d[u][e.to] = Some(e.weight);
            }
        }
    }

    for k in 0..n {
        for i in 0..n {
            let Some(dik) = d[i][k] else { continue };
            for j in 0..n {
                let Some(dkj) = d[k][j] else { continue };
                if d[i][j].is_none_or(|dij| dik + dkj < dij) {
                    d[i][j] = Some(dik + dkj);
                }
            }
        }
    }
    d
}

/// `ota` massividan `start → goal` yo'lini tiklaydi.
fn yolni_tikla(ota: &[Option<usize>], start: usize, goal: usize) -> Vec<usize> {
    let mut yol = vec![goal];
    let mut hozir = goal;
    while hozir != start {
        match ota[hozir] {
            Some(p) => {
                yol.push(p);
                hozir = p;
            }
            None => break,
        }
    }
    yol.reverse();
    yol
}

#[cfg(test)]
mod tests {
    use super::*;

    fn ogirlikli() -> Graph {
        let mut g = Graph::new_undirected(6);
        for (a, b, w) in [
            (0, 1, 7),
            (0, 2, 9),
            (0, 5, 14),
            (1, 2, 10),
            (1, 3, 15),
            (2, 3, 11),
            (2, 5, 2),
            (3, 4, 6),
            (4, 5, 9),
        ] {
            g.add_edge(a, b, w);
        }
        g
    }

    #[test]
    fn dijkstra_klassik_misol() {
        // Wikipediadagi mashhur misol: 0 dan 4 gacha eng qisqa masofa 20
        let g = ogirlikli();
        let d = dijkstra(&g, 0);
        assert_eq!(d[0], Some(0));
        assert_eq!(d[1], Some(7));
        assert_eq!(d[2], Some(9));
        assert_eq!(d[3], Some(20));
        assert_eq!(d[4], Some(20));
        assert_eq!(d[5], Some(11));
    }

    #[test]
    fn dijkstra_yolni_tiklaydi() {
        let g = ogirlikli();
        let (narx, yol) = dijkstra_path(&g, 0, 4).unwrap();
        assert_eq!(narx, 20);
        assert_eq!(yol.first(), Some(&0));
        assert_eq!(yol.last(), Some(&4));
        // yo'l bo'ylab og'irliklar yig'indisi narxga teng
        let jami: i64 = yol
            .windows(2)
            .map(|w| {
                g.neighbors(w[0])
                    .iter()
                    .filter(|e| e.to == w[1])
                    .map(|e| e.weight)
                    .min()
                    .unwrap()
            })
            .sum();
        assert_eq!(jami, narx);
    }

    #[test]
    fn yetib_bolmaydigan_tugun() {
        let mut g = Graph::new_undirected(3);
        g.add_edge(0, 1, 5);
        let d = dijkstra(&g, 0);
        assert_eq!(d[2], None);
        assert!(dijkstra_path(&g, 0, 2).is_none());
    }

    #[test]
    fn bellman_ford_manfiy_qirralar() {
        let mut g = Graph::new_directed(5);
        for (a, b, w) in [
            (0, 1, -1),
            (0, 2, 4),
            (1, 2, 3),
            (1, 3, 2),
            (1, 4, 2),
            (3, 2, 5),
            (3, 1, 1),
            (4, 3, -3),
        ] {
            g.add_edge(a, b, w);
        }
        let d = bellman_ford(&g, 0).unwrap();
        assert_eq!(d, vec![Some(0), Some(-1), Some(2), Some(-2), Some(1)]);
    }

    #[test]
    fn manfiy_siklni_aniqlaydi() {
        let mut g = Graph::new_directed(3);
        g.add_edge(0, 1, 1);
        g.add_edge(1, 2, -1);
        g.add_edge(2, 1, -1); // 1 → 2 → 1 = -2
        assert!(bellman_ford(&g, 0).is_none());
    }

    #[test]
    fn floyd_dijkstra_bilan_mos() {
        let g = ogirlikli();
        let fw = floyd_warshall(&g);
        for start in 0..g.node_count() {
            assert_eq!(fw[start], dijkstra(&g, start));
        }
    }

    #[test]
    fn bfs_eng_kam_qadamli_yol() {
        let mut g = Graph::new_undirected(7);
        for (a, b) in [(0, 1), (1, 2), (2, 3), (3, 6), (0, 4), (4, 5), (5, 6)] {
            g.add_unweighted_edge(a, b);
        }
        let yol = bfs_shortest_path(&g, 0, 6).unwrap();
        assert_eq!(yol.len(), 4); // 0 → 4 → 5 → 6
        assert_eq!(bfs_shortest_path(&g, 0, 0), Some(vec![0]));
    }
}