dijkstra's, a-star algorithm

Finds shortest path (path with min distance) from a node to a particular node or all nodes.

Start from the start node. Pick the node with lowest distance and update distance to its neighbors. Break out early to find min distance to end node only.

graph:

s 4 e
1   1
a 1 b

order of nodes: s, a, b, e
path: s, e (d = 3)

graph:

  1 a 9
s 2 b 7 e

order of nodes: s, a, b, e
path: s, b, e (d = 9)

graph:
    nodes
node:
    id
    neighbors

// O(vlogv + e)
dijkstra(g, start, end):
    dist = new map()
    dist[start.id] = 0
    previous = new map()
    unvisited = new min-heap(capacity: g.nodes.count(), x => x.dist[x.n.id])
    for n in g.nodes:
        unvisited.insert({n, dist})
    while !unvisited.isempty():
        n = unvisited.delete()
        //break early to find min distance to end only
        if n == end:
            break
        for neighbor in n.neighbors:
            //no need to update dist if neighbor is visited
            if !unvisited.has(neighbor.id):
                continue
            distneighbor = n.distance-to(neighbor) + dist[n.id]
            if dist[neighbor.id] == null || distneighbor < dist[neighbor.id]:
                dist[neighbor.id] = distneighbor
                previous[neighbor.id] = n
    if previous[end.id] == null:
        return null //no path
    path = new stack()
    path.push(end.id)
    n = end
    while n.id != start.id:
        n = previous[n.id]
        path.push(n)
    return tuple(dist[end.id], path))

For A*, don't update the neighbor's distance if not within limit. If no path exists within limit then n's distance will be null (infinity).

// O(vlogv + e)
a-star(g, start, end, limit):
    dist = new map()
    dist[start.id] = 0
    previous = new map()
    unvisited = new min-heap(capacity: g.nodes.count(), x => x.dist[x.n.id])
    for n in g.nodes:
        unvisited.insert({n, dist})
    while !unvisited.isempty():
        n = unvisited.delete()
        //no path exists within limit
        if dist[n.id] == null:
            break
        //break early to find min distance to end only
        if n == end:
            break
        for neighbor in n.neighbors:
            //no need to update dist if neighbor is visited
            if !unvisited.has(neighbor.id):
                continue
            distneighbor = n.distance-to(neighbor) + dist[n.id]
            if (dist[neighbor.id] == null || distneighbor < dist[neighbor.id])
                && distneighbor <= limit:
                dist[neighbor.id] = distneighbor
                previous[neighbor.id] = n
    if previous[end.id] == null:
        return null //no path
    path = new stack()
    path.push(end.id)
    n = end
    while n.id != start.id:
        n = previous[n.id]
        path.push(n)
    return tuple(dist[end.id], path))

[Hat tip to SM]