CSE 373 Section 7

Dijkstra’s + Graph Modeling

Challenge Problem

Challenge Problem

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Constraints: 1 <= N <= 200, M[i][i] == 1, M[i][j] == M[j][i]

​

,

• M[i][i] == 1
• M[i][j] == M[j][i]

​

​

​

​

​

MicroTeach: Dijkstra’s

Dijkstra’s Algorithm

• Pathfinding on a weighted graph!�
• Main idea: find shortest path/shortest distance from start node in graph to every other node.�
• Uses a Priority Queue, where priorities of nodes are their distance from the start node�
• We pull the closest node off the queue each iteration, and update the distances for its adjacent nodes. Then repeat.

​

Dijkstra’s Pseudocode

Dijkstra(Graph G, Vertex source)

initialize distances to ∞

mark all vertices unprocessed

mark source as distance 0

while(there are unprocessed vertices){

let u be the closest unprocessed vertex

for each(edge (u,v) leaving u){

if(u.dist+weight(u,v) < v.dist){

v.dist = u.dist+weight(u,v)

v.predecessor = u

}

}

mark u as processed

}

Q: How to get the shortest path?

A: After running Dijkstra, start from the target node and follow the backpointers!�

GetPath(Graph G, Vertex source, Vertex target)

// We never reached the target :(

if (target.dist == INFINITY)

return null

path = []

curNode = target

path.add_back(target)

​

while(curNode != source)

curNode = curNode.predecessor

path.add_back(curNode)�

// If we want the path to go from source -> goal.

return path.reversed()

​

BFS vs. Dijkstra SPT Side to Side Comparison

Dijkstra(Graph G, Vertex source)

initialize distances to ∞

mark all vertices unprocessed

mark source as distance 0

while(there are unprocessed vertices){

let u be the closest unprocessed vertex

for each(edge (u,v) leaving u){

if(u.dist+weight(u,v) < v.dist){

v.dist = u.dist+weight(u,v)

v.predecessor = u

}

}

mark u as processed

}

GetPath(Graph G, Vertex source, Vertex target)

// We never reached the target :(

if (target.dist == INFINITY)

return null

path = []

curNode = target

path.add_back(target)

​

while(curNode != source)

curNode = curNode.predecessor

path.add_back(curNode)�

// If we want the path to go from source -> goal.

return path.reversed()

​

​

BFS implements “fake” distances to be able to backtrace and find the SPT

Problem 1 (Dijkstra)

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

(Nothing happens!)

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

(Nothing happens!)

Problem 4A: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Problem 1: Dijkstra

Y

S

Z

T

X

6

7

8

9

7

3

2

5

4

Resulting SPT

Why It Works - Understanding Dijkstra Invariants

Invariants

predecessor[v]: best known predecessor of v.

distance[v]: best known distance of s to v.

PQ maintains vertices based on distance.

​

Important properties

Always visits vertices in order of total distance from source.

​

Problem 2: Buggy Dijkstra

Problem 2

​

What lines look incorrect?

Problem 2: Breaking down bug #1

​

Returning once we find “end” in neighbors

Start

End

A

900

1

2

What’s the fix?

Return once we “choose” end in the outer loop!

Path to end:

Start→?

Weight:

0?

Problem 2

​

The second bug

Problem 2: Breaking down bug #1

​

Only adding the edge weight “w” to edgeTo

Start

End

A

8

1

2

What’s the fix?

Add newDist to distTo!

Path to end:

Start->A->End

Weight:

2

Problem 3: DJ Kistra

Problem 3

​

Problem 3

​

(a) Describe a graph you could construct to help you solve the problem. At the very least you’ll want to mention what the vertices and edges are, and whether the edges are weighted or unweighted and directed or undirected.

Problem 3

​

Q: How do we get from Shake It Off to Wildest Dreams while obeying the rule:

​

Two consecutive songs’ tempos must differ by no more than 10 beats per minute (BPM)

Shake It Off

Wildest Dreams

Problem 3

​

Shake It Off

Let vertices be songs!

Love

Song

22

Lover

Wildest Dreams

But how do we know if two songs’ tempos differ by more than 10 BPM?

Problem 3

​

Shake It Off

150 BPM

Include BPM in vertices!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Storing multiple pieces of information in Vertex or Edge Objects is often useful.

Problem 3

​

Shake It Off

150 BPM

Q: What are our edges?

​

We know we want to slow down the tempo and create a path between Shake It Off and Wildest Dreams.

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Problem 3

​

Shake It Off

150 BPM

Let edges represent valid song transitions!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

Problem 3

​

Shake It Off

150 BPM

Let edges represent valid song transitions!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

valid?

Problem 3

​

Shake It Off

150 BPM

Let edges represent valid song transitions!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Directed or Undirected?

​

Directed: We don’t want to play a song we already played since it has a faster tempo and is farther away from Wildest Dreams.

Problem 3

​

💯

👀

Can we accomplish the task with the graph model we’ve built? Let’s check.

There’s more information we haven’t used. Does the length of the songs help us?

We don’t have a way to prioritize between different possible song transitions!

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Q: Once we have edges, how do we know which path between Shake It Off and Wildest Dreams will take the least amount of time?

​

Looks like we need to encode more information in our graph.

Problem 3

​

Shake It Off

150 BPM

Let edge weights be the length of the next song!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Let’s think ahead: why does this help us decide which path will take the shortest amount of time?

​

We’ll use this information later when we run an algorithm on our graph to find the list of songs that take the least time.

237 sec.

Problem 3

​

Shake It Off

150 BPM

Let edge weights be the length of the next song!

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Which algorithm can make use of edge weights to give us a shortest path?

237 sec.

Dijkstra’s!

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Now our graph model has everything it needs to find the shortest path between Shake It Off and Wildest Dreams!

237 sec.

Vertices: song and BPM

​

Edges: valid song transitions

​

Weights: next song length

Problem 3

​

(b) Describe an algorithm to construct your graph from the previous part. You may assume your songs are stored in whatever data structure makes this part easiest. Assume you have access to a method makeEdge(v1, v2, w) which creates an edge from v1 to v2 of weight w.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

valid?

Let’s continue making edges and see if we can turn the process into an algorithm.

237 sec.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

valid?

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

​

237 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

valid?

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Allow the DJ to play the next song only if its tempo is slower and within 10 BPM of the current song.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

valid?

valid?

valid?

valid?

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

Are these valid?

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

Are these valid?

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

222 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

222 sec.

Are these valid?

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Algorithm: Check every pair of vertices and add an edge if it’s valid.

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

222 sec.

Problem 3

​

Shake It Off

150 BPM

Love

Song

140 BPM

22

150 BPM

Lover

130 BPM

Wildest Dreams

120 BPM

Ta-da! This is our graph :)

Vertices: song and BPM

Edges: valid song transitions

Weights: next song length

237 sec.

205 sec.

187 sec.

222 sec.

Problem 3

​

Problem 3

​

(c) Describe an algorithm you could run on the graph you just constructed to find the list of songs you can play to get to “Wildest Dreams” the fastest without disappointing the crowd.

Problem 3

​

(d) What is the running time of your plan to find the list of songs? You should include the time it would take to construct your graph and to find the list of songs. Give a simplified big-O running time in terms of whatever variables you need.

Problem 3

​

How long did it take to construct our graph?

​

​

We then run Dijkstra’s starting from Shake It Off. What’s the runtime of Dijkstra’s?

O(S²)

O(E*log(S) + S*log(S))

O(S² + E*log(S) + S*log(S))

What’s the total runtime to find the list of songs the DJ should play?

Is this simplified?

S² dominates S*log(S) so we can ignore the smaller term!

Total runtime: O(S² + E*log(S))

Bellman-Ford Algorithm

Bellman-Ford Algorithm

• Pathfinding on a weighted graph!�
• Main idea: find shortest path/shortest distance from start node in graph to every other node.�
• Unlike Dijkstra’s Algorithm, Bellman-Ford works on graphs with negative weight edges �
• The biggest challenge to finding the shortest path is the existence of negative cycles. Bellman-Ford terminates upon finding a negative cycle.

​

Bellman-Ford Algorithm Pseudocode

BellmanFord(Graph G, Start Node S)

for each vertex V in G

for each edge (U, V) in G

tempDistance <- distance[U] + edge_weight(U, V)

if tempDistance < distance[V]

distance[V] <- tempDistance

previous[V] <- U

for each edge (U,V) in G

if distance[U] + edge_weight(U, V) < distance[V]

Error: Negative Cycle Exists

return distance[], previous[]

​

Bellman-Ford vs Dijkstra’s

• Both algorithms are very similar in structure. While Dijkstra’s looks only to the immediate neighbors of a vertex, Bellman goes through each edge in every iteration.

​

​

Challenge Problem Solution

Challenge Problem Solution

​

​

​

​

​

​

• Understanding the question
• How is this problem expressing the relationship between friends?

​

Adjacency List Adjacency Matrix

​

​

• Memory usage depends on the number of edges (not number of nodes),�which might save a lot of memory if the adjacency matrix is sparse
• Finding the presence or absence of specific edge between any two nodes�is slightly slower than with the matrix O(k); where k is the number of neighbors nodes
• It is fast to iterate over all edges because you can access any node neighbors directly
• It is fast to add/delete a node; easier than the matrix representation
• It fast to add a new edge O(1)

​

• Uses O(n^2) memory
• It is fast to lookup and check for presence or absence of a specific edge�between any two nodes O(1)
• It is slow to iterate over all edges
• It is slow to add/delete a node; a complex operation O(n^2)
• It is fast to add a new edge O(1)

​

Challenge Problem Solution

​

​

• What algorithm do we need to need to implement out “Explore” idea?

Challenge Problem Solution

​

​

​

• DFS
• Imagine you put your pencil at one point and you continue to explore until you reach the dead end without lifting your pencil
• This could be used to figure out our cur index’s friends connection
• Start from one person and continue to explore friend’s friend and repeat until the connection ends
• We don’t want to visit already marked relationship

​

​

​

• We made important connection with general dfs algorithm and our desirable implementation

​

​

​

​

Challenge Problem Solution

​

​

This can be done in bfs as well!

Challenge Problem Solution

​

​