algorithms_fourth 0.1.10

//! DijKstraSp算法查找最短路径
//! ## 限制条件
//! 权重非负
//! ## 思路
//! 原点为只有一个节点的最短路径树，以树中节点到原点的权重排序，
//! 依次取出下一个可扩充树的节点，此时记录的原点到该节点的权重一定是两节点间的最小权重,
//! 然后扩展树，提取下一个节点，直到所有节点的最短路径都获取到
//!
//! ## 使用
//! ```
//!     use algorithms_fourth::{ add_edge_weighted_for_digraph,
//!  digraph::{dijkstra_sp::DijkstraSP, edge_weighted::EdgeWeigtedDigraph}, };

//!         let mut g = EdgeWeigtedDigraph::new(8);
//!         add_edge_weighted_for_digraph!(g, 5, 4, 0.35);
//!         add_edge_weighted_for_digraph!(g, 4, 7, 0.37);
//!         add_edge_weighted_for_digraph!(g, 5, 7, 0.28);
//!         add_edge_weighted_for_digraph!(g, 5, 1, 0.32);
//!         add_edge_weighted_for_digraph!(g, 4, 0, 0.38);
//!         add_edge_weighted_for_digraph!(g, 0, 2, 0.26);
//!         add_edge_weighted_for_digraph!(g, 3, 7, 0.39);
//!         add_edge_weighted_for_digraph!(g, 1, 3, 0.29);
//!         add_edge_weighted_for_digraph!(g, 7, 2, 0.34);
//!         add_edge_weighted_for_digraph!(g, 6, 2, 0.40);
//!         add_edge_weighted_for_digraph!(g, 3, 6, 0.52);
//!         add_edge_weighted_for_digraph!(g, 6, 0, 0.58);
//!         add_edge_weighted_for_digraph!(g, 6, 4, 0.93);
//!         if false {
//!             g.print_dot("e.dot");
//!         }
//!         let sp = DijkstraSP::new(&g, 5);
//!         assert_eq!(sp.dist_to(6), 1.13);
//!         assert_eq!(sp.dist_to(4), 0.35);
//!         assert_eq!(sp.dist_to(2) as f32, 0.62);
//!         for e in sp.path_to(2).unwrap(){
//!             println!("{:?}",e);            
//!         }
//!
//! ```
use crate::priority_queue::IndexPQ;

use super::edge_weighted::{DirectedEdge, EdgeWeigtedDigraph, Weight};

pub struct DijkstraSP<'a> {
    edge_to: Vec<Option<&'a DirectedEdge>>,
    dist_to: Vec<Weight>,
    pq: IndexPQ<Weight>,
}
impl<'a> DijkstraSP<'a> {
    pub fn new(g: &'a EdgeWeigtedDigraph, s: usize) -> Self {
        let mut edge_to = Vec::with_capacity(g.vertex_count());
        for _ in 0..g.vertex_count() {
            edge_to.push(None);
        }
        let dist_to = vec![Weight::MAX; g.vertex_count()];
        let pq = IndexPQ::new_min_pq(g.vertex_count());
        let mut sp = DijkstraSP {
            edge_to,
            dist_to,
            pq,
        };
        sp.dist_to[s] = 0.0;
        sp.pq.push(s, 0.0);
        while let Some((k, _)) = sp.pq.pop() {
            sp.relax(g, k);
        }
        sp
    }

    fn relax(&mut self, g: &'a EdgeWeigtedDigraph, v: usize) {
        for e in g.adj(v) {
            let w = e.to();
            let p = self.dist_to[v] + e.weight();
            if self.dist_to[w] > p {
                self.dist_to[w] = p;
                self.edge_to[w] = Some(e);
                if self.pq.contains(w) {
                    self.pq.change(w, p);
                } else {
                    self.pq.push(w, p);
                }
            }
        }
    }
    pub fn dist_to(&self, v: usize) -> Weight {
        self.dist_to[v]
    }
    pub fn has_path_to(&self, v: usize) -> bool {
        self.dist_to(v) < Weight::MAX
    }
    pub fn path_to(&self, v: usize) -> Option<std::iter::Rev<std::vec::IntoIter<&DirectedEdge>>> {
        if self.has_path_to(v) {
            let mut path = Vec::new();
            let mut c = self.edge_to.get(v);
            while let Some(&Some(e)) = c {
                path.push(e);
                c = self.edge_to.get(e.from());
            }
            Some(path.into_iter().rev())
        } else {
            None
        }
    }
}

#[cfg(test)]
mod test {
    use crate::{
        add_edge_weighted_for_digraph,
        digraph::{dijkstra_sp::DijkstraSP, edge_weighted::EdgeWeigtedDigraph},
    };

    #[test]
    fn test() {
        let mut g = EdgeWeigtedDigraph::new(8);
        add_edge_weighted_for_digraph!(g, 5, 4, 0.35);
        add_edge_weighted_for_digraph!(g, 4, 7, 0.37);
        add_edge_weighted_for_digraph!(g, 5, 7, 0.28);
        add_edge_weighted_for_digraph!(g, 5, 1, 0.32);
        add_edge_weighted_for_digraph!(g, 4, 0, 0.38);
        add_edge_weighted_for_digraph!(g, 0, 2, 0.26);
        add_edge_weighted_for_digraph!(g, 3, 7, 0.39);
        add_edge_weighted_for_digraph!(g, 1, 3, 0.29);
        add_edge_weighted_for_digraph!(g, 7, 2, 0.34);
        add_edge_weighted_for_digraph!(g, 6, 2, 0.40);
        add_edge_weighted_for_digraph!(g, 3, 6, 0.52);
        add_edge_weighted_for_digraph!(g, 6, 0, 0.58);
        add_edge_weighted_for_digraph!(g, 6, 4, 0.93);
        if false {
            g.print_dot("e.dot");
        }
        let sp = DijkstraSP::new(&g, 5);
        assert_eq!(sp.dist_to(6), 1.13);
        assert_eq!(sp.dist_to(4), 0.35);
        assert_eq!(sp.dist_to(2) as f32, 0.62);
        for e in sp.path_to(2).unwrap() {
            println!("{:?}", e);
        }
    }
}