A* Heuristic Admissibility Check

Problem

Check whether a heuristic is admissible for A* search: h(v) must never exceed the true shortest distance from v to goal.

Compute exact distances to goal by running Dijkstra on the reversed graph, then compare. Negative heuristic values are never admissible. edges is a list of [u, v, w] triples and heuristic is a list of n values.

Hint

Run Dijkstra backwards from the goal to obtain the exact distances for comparison.

Test cases

case 1

in: [3,[[0,1,1],[1,2,1]],2,[2,1,0]]

expected: true

case 2

in: [3,[[0,1,1],[1,2,1]],2,[3,1,0]]

expected: false

case 3

in: [3,[[0,1,1],[1,2,1]],2,[-1,1,0]]

expected: false

case 4

in: [4,[[0,1,2],[1,3,2],[2,3,0]],3,[4,2,7,0]]

expected: false

case 5

in: [2,[[0,1,5]],1,[5,0]]

expected: true

Starter codePython

import heapq
def is_admissible(n, edges, goal, heuristic):
    # Your code here
    pass

5 test cases · run your code against them in the editor