Solve InterviewCake.com's mesh-message problem

Write a function that returns the shortest path between nodes A and B in an
unweighted graph.

I know two algorithms for finding the shortest path in a *weighted* graph:
- Use a heap as a priority queue instead of the regular queue that you would use
  when doing a BFT. This is called Dijkstra's algorithm. You can also use
  Dijkstra's algorithm in an unweight graph by imaginging that all of the
  weights on the edges are the same value (e.g. 1).
- Map the weighted graph into an unweighted graph by inserting N nodes between
  each node, X and Y, where N is equal to the weight of the edge between X and
  Y. After you map the weighted graph into an unweighted graph, perform a BFT
  from A to B. A BFT will always find the shortest path between nodes A and B in
  an unweighted graph.

I had forgotten that a BFT in an unweighted graph will always return the
shortest path between two nodes. I learned two things from InterviewCake.com's
solution:
1. I remembered that a BFT in an unweighted graph will return the shortest
   path (if one exists).
2. I learned to use a dictionary to store the edge information and then
   back-tracking to reconstruct the shortest path.

0 files changed, 0 insertions, 0 deletions