# Finding the Must-pass, Shortest Path Nodes in a Graph

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; // stores distance of each node from root

int[][] bftid = g.bfs(tId);
int[] tidistance = bftid; // 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.