A* Algorithm Quickest Time

Question

I've implemented the A* Algorithm to give the shortest distance route, however I'm trying to alter that so it will calculate the quickest route. Using this pseudocode:

function A*(start,goal)
    closedset := the empty set    // The set of nodes already evaluated.
    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
    came_from := the empty map    // The map of navigated nodes.

    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while openset is not empty
        current := the node in openset having the lowest f_score[] value
        if current = goal
            return reconstruct_path(came_from, goal)

        remove current from openset
        add current to closedset
        for each neighbor in neighbor_nodes(current)
            if neighbor in closedset
                continue
            tentative_g_score := g_score[current] + dist_between(current,neighbor)

            if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g_score
                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                if neighbor not in openset
                    add neighbor to openset

    return failure

I thought that the easiest way to calculate the quickest route would be to divide the distance between current and neighbour by the speed limit of that road: tentative_g_score := g_score[current] + (dist_between(current,neighbor)/neighbor.speedlimit) However this doesn't give the correct result in my algorithm.

Can anyone possibly point me in the right direction as to how to do this efficiently?

Here is my current code: http://pastebin.com/QWi6AwF9

Quickest route as in, one that takes the least time to reach the destination from the start location.

My heuristic function is this

private double heuristic(Vertex goal, Vertex next) 
    {
        return (Math.sqrt(Math.pow((goal.x - next.x), 2) + Math.pow((goal.y - next.y), 2)));
    }

Cheers

Answer 1

The heuristic function must be admissible(that is, it should never overestimate the distance to the goal). Once you start dividing the length of an edge by speedlimit, the real distance to the goal might be less than the Euclidean distance to it(if speedlimit > 1). It breaks the algorithm. How to fix it? For example, you can use dist / MAX_SPEED_LIMIT as a heursitic function instead.