A* fails to find optimal solution with admissible but inconsistent heuristic

[lillanes]

A* using an admissible but inconsistent heuristic should find optimal paths. The current implementation seems to assume that heuristics will always be consistent, and fails to find optimal paths in some cases.

Test Case

use petgraph::prelude::*;
use petgraph::algo::astar;

#[test]
fn test_astar_admissible_inconsistent() {
    let mut g = Graph::new();
    let a = g.add_node("A");
    let b = g.add_node("B");
    let c = g.add_node("C");
    let d = g.add_node("D");
    g.add_edge(a, b, 3);
    g.add_edge(b, c, 3);
    g.add_edge(c, d, 3);
    g.add_edge(a, c, 8);
    g.add_edge(a, d, 10);

    let admissible_inconsistent = |n: NodeIndex| match g[n] {
        "A" => 9,
        "B" => 6,
        "C" => 0,
        &_ => 0,
    };

    let optimal = astar(&g, a, |n| n == d, |e| *e.weight(), admissible_inconsistent);
    assert_eq!(optimal, Some((9, vec![a, b, c, d])));
}

Steps To Reproduce

See above.

Actual Results

astar finds the path A->D with cost 10.

Expected Results

The algorithm should find the optimal path A->B->C->D with cost 9.

[bluss]

Fixed by #379