A* Landmark Heuristic

Problem

Build a landmark heuristic for A*: h(v) = |dist(landmark, v) - dist(landmark, goal)|.

Run Dijkstra from the landmark on the undirected weighted graph, then return the heuristic for every node in order. Nodes or goals disconnected from the landmark get -1. edges is a list of [u, v, w] triples.

Hint

Landmark heuristics stay admissible because distances obey the triangle inequality.

Test cases

case 1

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

expected: [6,4,3,0]

case 2

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

expected: [2,1,0,1]

case 3

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

expected: [-1,-1,-1]

Starter codePython

import heapq
def landmark_heuristic(n, edges, landmark, goal):
    # Your code here
    pass

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