Directed Graph

Question 1

Djikstra’s algo to find shortest path in weighted graph

Q: given prices of flights, find the cheapest way to go from source to destination within K stops, if no such route exists, return -1

Answer 1

Build the graph:
Map<Integer, List<Pair<Integer, Integer»> graph = new HashMap<>(); //from -> (to, cost)

store number of stops to get to each city from source
int[] stops = new int[n];
Arrays.fill(stops, Integer.MAX_VALUE);

Priority Queue to get the edge with lowest weight/cost
PriorityQueue<int[]> minHeap = new PriorityQueue<>();
heap.add(new int[]{src, 0, 0}); //city, cost, number of stops from src

djikstras:
while(!minHeap.isEmpty()) {
int[] polled = heap.poll();
int city = polled[0];
int cost = polled[1];
int numberStops = polled[2];
if (numberOfStops > k+ 1 || stops[city] <= numberOfStops) continue;

stops[city] = numberOfStops;

if (city == destination) return cost;

for(Pair<Integer, Integer> pair: graph.getOrDefault(city, new ArrayList<>())) {
   int childCity = pair.getKey();
   int weight = pair.getValue();
   heap.add(new int[]{childCity, weight + cost, numberStops+1});
} }

return -1;

Question 2

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

Answer 2

Use topological sort and return true if the graph made by the edges given by prereq gives a DAG

    Map<Integer, Set<Integer>> edges = new HashMap<>(); //a -> b means we take b after a
    Map<Integer, Integer> inDegree = new HashMap<>();
    for(int index=0; index<numCourses; index++) {
        inDegree.put(index, 0);
    }
    for(int[] edge: prerequisites) {
        edges.putIfAbsent(edge[1], new HashSet<>());
        edges.get(edge[1]).add(edge[0]);
        inDegree.put(edge[0], inDegree.get(edge[0])+1);
    }
    Queue<Integer> queue = new LinkedList<>();
    for(int index=0; index<numCourses; index++) {
        if (inDegree.get(index)==0) {
            queue.add(index);
            inDegree.remove(index);
        }
    }
    while(!queue.isEmpty()) {
        int course = queue.poll();
        for(int child: edges.getOrDefault(course, new HashSet<>())) {
            if (inDegree.get(child)==1) {
                inDegree.remove(child);
                queue.add(child);
            } else {
                inDegree.put(child, inDegree.get(child)-1);
            }
        }
    }
    return inDegree.isEmpty();