/MustPassNodes

My solution to the Must pass nodes in a shortest path problem

Primary LanguageJava

Must Pass Nodes

Problem

You are given a graph and two vertices s and t. Implement a linear time algorithm that finds all the vertices u such that all shortest paths from s to t pass through u.

Implementation

  • Class Lab3 contains the three function problem. Implement solutions in this function.
  • Do NOT make changes outside these functions.
  • Graph class contains BFS and DFS functions. Use BFS.
  • Implement in linear run time