CSE 373 SP25 AX Section 8
Graph Algorithms and Design
Check-In
What is the last video game you played?
Announcements
Dijkstra’s Algorithm: single-pair-shortest-path
Dijkstra’s Review
Buggy Dijkstra’s
dijkstraShortestPath(G graph, V start, V end)
Set known; Map edgeTo, distTo;
initialize distTo with all nodes mapped to infinity, except start to 0
while (there are unknown vertices):
let u be the closest unknown vertex
known.add(u)
for each edge (u,v) to unknown v with weight w:
if (v == end)
return path // We found the goal node, we’re done!
oldDist = distTo.get(v)
newDist = distTo.get(u) + w
if (newDist < oldDist):
distTo.put(v, w)
edgeTo.put(v, u)
Buggy Dijkstra’s - Solution (Link)
Run Dijkstra’s algorithm on the graph below starting at the vertex 0. The table to the right shows the results right after 2’s edges have been relaxed.
vertex | distTo | edgeTo |
0 | 0 | - |
1 | ∞ | - |
2 | 5 | 4 |
3 | 1 | 0 |
4 | 4 | 0 |
5 | 8 | 2 |
6 | 6 | 4 |
7 | 2 | 3 |
2
0
1
3
4
5
6
7
8
2
4
1
5
1
3
9
1
3
3
1
20
Shortest Paths (solution)
Suppose that we run Dijkstra’s algorithm on the graph below from the vertex 0.
The table to the right shows the results right after vertex 2’s edges have been relaxed.
vertex | distTo | edgeTo |
0 | 0 | - |
1 | ∞ | - |
2 | 5 | 4 |
3 | 1 | 0 |
4 | 4 | 0 |
5 | 8 | 2 |
6 | 6 | 4 |
7 | 2 | 3 |
Shortest Paths (solution)
c. Update the table after the vertex you identified from (b) is visited (i.e. after all its edges are relaxed).
vertex | distTo | edgeTo |
0 | 0 | - |
1 | 26 | 6 |
2 | 5 | 4 |
3 | 1 | 0 |
4 | 4 | 0 |
5 | 7 | 6 |
6 | 6 | 4 |
7 | 2 | 3 |
Graph Design Scenarios
Graph Design: Scenario 1
Anna is commuting from her home to campus to teach lecture. However, before stepping foot in the lecture hall, she needs to print out the lecture worksheets. With this in mind, Anna is trying to calculate the shortest path she can take from her house to the lecture hall that includes a stop at a printer. How might she achieve this?
Graph Design: Scenario 1 Solution
Graph Design: Scenario 1 Solution
Run Dijkstra’s from Anna’s house to get the shortest path to every printer. Then, run Dijkstra’s again from the lecture hall to find the shortest path from there to every printer.
Aelysha’s Drawing:
Graph Design: Scenario 1 Solution
Run Dijkstra’s from Anna’s house to get the shortest path to every printer. Then, run Dijkstra’s again from the lecture hall to find the shortest path from there to every printer.
Aelysha’s Drawing:
Graph Design: Scenario 2
Anna is walking her dog Percy and knows Percy's favorite spots to use the bathroom. She wants to try to make it home whilst simultaneously minimizing the amount of times that she has to stop and let Percy use the bathroom. Return any 5 distinct paths Anna can take to get to her house that minimize the amount of times she has to stop and let Percy use the bathroom.
Graph Design: Scenario 2 Solution
Graph Design: Scenario 2 Solution
Aelysha’s Drawing:
Graph Design: Scenario 3
Suppose we are trying to design a maze within a 2d top-down video-game. The world is represented as a grid, where each tile is either an impassable wall, an open space a player can pass through, or a wormhole. On each turn, the player may move one space on the grid to any adjacent open tile. If the player is standing on a wormhole, they can instead use their turn to teleport themselves to the other end of the wormhole, which is located somewhere else on the map.
Now, suppose that there are several coins scattered throughout the map. Your goal is to design an algorithm that finds a path between the player and some coin in the fewest number of turns possible.
Scenario 3 - Solution (Link)
Leetcode - Graphs!
Why LeetCode Style Code Challenges?
Instructions
Each group of 3 or 4 students will be assigned the following problem:
Different Approaches to Use:
For instructions, search online for the problem by ID number, e.g. “LeetCode 347”.
We will have about 20 minutes for this activity:
NO NEED to write up code for this activity. Try to come up with solution approaches and how you would tackle the program on the high-level using specific data structures.
Different Approaches Available
Presentation Guidelines
Questions to Ask Yourself:
Presentation Guidelines
Complete the reflection activity in Gradescope and add your groupmates!
Example Solution - LeetCode 994 (Super-Source BFS Trick)
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] visited = grid;
Queue<int[]> q = new LinkedList<>();
int countFreshOrange = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == 2) {
q.offer(new int[] {i, j});
}
if (visited[i][j] == 1) {
countFreshOrange++;
}
}
}
if (countFreshOrange == 0)
return 0;
if (q.isEmpty())
return -1;
int minutes = -1;
int[][] dirs = {{1, 0},{-1, 0},{0, -1},{0, 1}};
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
int[] cell = q.poll();
int x = cell[0];
int y = cell[1];
for (int[] dir : dirs) {
int i = x + dir[0];
int j = y + dir[1];
if (i >= 0 && i < m && j >= 0 && j < n && visited[i][j] == 1) {
visited[i][j] = 2;
countFreshOrange--;
q.offer(new int[] {i, j});
}
}
}
minutes++;
}
if (countFreshOrange == 0)
return minutes;
return -1;
}
}
Example Solution - LeetCode 743 (Min-Heap Dijkstra’s Algorithm)
public int networkDelayTime_Dijkstra(int[][] times, int N, int K) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int[] edge: times) {
graph.putIfAbsent(edge[0], new ArrayList<>());
graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
boolean[] visited = new boolean[N + 1];
int[] minDis = new int[N + 1];
Arrays.fill(minDis, Integer.MAX_VALUE);
minDis[K] = 0;
pq.offer(new int[]{0, K});
int max = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int currNode = curr[1];
if (visited[currNode]) continue;
visited[currNode] = true;
int currDis = curr[0];
max = currDis;
N--;
if (!graph.containsKey(currNode)) continue;
for (int[] next : graph.get(currNode)) {
if (!visited[next[0]] && currDis + next[1] < minDis[next[0]])
pq.offer(new int[]{currDis + next[1], next[0]});
}
}
return N == 0 ? max : -1;
}
Reference Slide - DFS
dfs(Graph graph, Vertex start) {
Stack<Vertex> perimeter = new Stack<>();
Set<Vertex> visited = new Set<>();
perimeter.add(start);
while (!perimeter.isEmpty()) {
Vertex from = perimeter.remove();
if (!visted.contains(from)) {
for (Edge edge:graph.edgesFrom(from)) {
Vertex to = edge.to();
perimeter.add(to)
}
visited.add(from);
}
}
}
Reference Slide - BFS
...
Map<Vertex, Edge> edgeTo = ...
Map<Vertex, Double> distTo = ...
edgeTo.put(start, null);
distTo.put(start, 0.0);
while (!perimeter.isEmpty()) {
Vertex from = perimeter.remove();
for (Edge edge : graph.edgesFrom(from)) {
Vertex to = edge.to();
if (!visited.contains(to)) {
edgeTo.put(to, edge);
distTo.put(to, distTo.get(from) + 1);
perimeter.add(to);
visited.add(to);
}
}
}
return edgeTo;
}
Reference Slide - Dijkstra’s (Pseudocode)
dijkstraShortestPath(G graph, V start)
Set known; Map edgeTo, distTo;
initialize distTo with all nodes mapped to ∞, except start to 0
while (there are unknown vertices):
let u be the closest unknown vertex
known.add(u)
for each edge (u,v) to unknown v with weight w:
oldDist = distTo.get(v) // previous best path to v
newDist = distTo.get(u) + w // what if we went through u?
if (newDist < oldDist):
distTo.put(v, newDist)
edgeTo.put(v, u)
Closing Announcements
Please don't hesitate to reach out if you have any
questions or concerns about the course, or if there's
anything else we can help you with! We're here to support
you however we can!