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

Leave a Reply

Your email address will not be published. Required fields are marked *