Week 4 of Coursera's Advanced Data Structures in Java

A* algorithm.md

Dijkstra's Algorithm

PQ ordering is based on: g(n): the distance (cost) from start vertex to vertex n.

A* algorithm

PQ ordering is based on: g(n): the distance (cost) from start vertex to vertex n AND h(n): the heuristic estimated cost from vertex n to goal vertex.
f(n) = g(n) + h(n)

Dijkstra's Algorithm.md

Dijkstra: Algorithm

S: Source Vertex, G: Goal Vertex
Dijkstra(S, G):
  Initialize: Priority queue (PQ), visited HashSet, parent HashMap, and distances to infinity // o(|v|)
  Enqueue {S, 0} onto the PQ // o(1)
  while PQ is not empty:
    dequeue node curr from front of queue
    if(curr is not visited)
      add curr to visited set
      if curr == G return parent map
      for each of curr's neighbors, n, not in visited set:
        if path through curr to n is shorter
          update n's distance
          update curr as n's parent in parent map
          enqueue {n, distance} into the PQ
  // If we get here then there's no path

Note: Larger distances are lower priority.

Running time

• Line 5: o(|v|)
• Line 6: o(1)
• Line 7: o(|E|)
• Line 8 and line 16: o(log|E|)
• Overall : o(|E|log|E| + |v|)
• Because E <= |V|^2 and log(|V|^2) is just O(log(|V|)), we could tighten to: O(|E|log|V| + |V|).