A* F-Scores

Problem

Compute the A* f-score f(v) = g(v) + h(v) of every node, where g(v) is the true shortest distance from start and h is the given heuristic.

Use Dijkstra from start for g. Return f-scores in node order, or -1 for nodes unreachable from start. edges is a list of [u, v, w] triples.

Hint

The f-score combines what a path already cost with the heuristic estimate of what remains.

case 1

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

expected: [3,3,5,2]

case 2

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

expected: [4,4,4]

case 3

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

expected: [1,1,-1]

case 4

in: [1,[],0,[0]]

expected: [0]

Starter codePython

import heapq
def astar_f_scores(n, edges, start, heuristic):
    # Your code here
    pass

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