The following is a problem given as a lab assignment for my Graph Algorithms course that I’m currently taking. It’s a pretty interesting problem and I enjoyed coming up with the solution.

**Problem**

Fatima commutes from KTH to home by subway every day. Today Robert decided to surprise Fatima by baking cookies and bringing them to an intermediate station. Fatima does not always take the same route home, because she loves to admire the artwork inside different stations in Stockholm. However, she always optimizes her travel by taking the shortest route. Can you tell Robert which station he should go to in order to surely intercept Fatima?

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*.

**Solution**

private static int[] problem(Graph g, int sId, int tId) { // store bfsId results int[][] bfsid = g.bfs(sId); int[] sidistance = bfsid[0]; // stores distance of each node from root int[][] bftid = g.bfs(tId); int[] tidistance = bftid[0]; // stores distance of each node from destination // data for while loop int V = tId; // mark required vertices boolean[] includeNode = new boolean[g.noOfVertices]; // stores info on vertices in the interval HashMap<Integer, Integer> interval = new HashMap<Integer, Integer>(); int sPathLen = sidistance[tId]; int solutionLen = 0; // this is the layering part for (int i = 0; i < g.noOfVertices; i++) { int sdist = sidistance[i]; int dist = sdist + tidistance[i]; if (dist == sPathLen) { // if there is another node in the same layer, we don't want to include it if (interval.containsKey(sdist)) { // make sure we don't decrement if we already have for this vertex if (includeNode[interval.get(sdist)]) solutionLen--; includeNode[interval.get(sdist)] = false; } else { interval.put(sdist, i); includeNode[i] = true; solutionLen++; } } } int outIndex = 0; int[] solution = new int[solutionLen]; // add must-pass nodes to the solution for (int i = 0; i < g.noOfVertices; i++) { if (includeNode[i]) { solution[outIndex] = i; outIndex++; } } return solution; }

To find the full problem description as well as all the project files, visit here.