Network Algorithms Flashcards

(4 cards)

1
Q

How do you carry out Kruskal’s algorithm?

Minimum spanning network

A
  • Select shortest edge
  • Select next shortest edge that doesn’t create a cycle until all vertices are connected
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How do you carry out Prim’s algorithm?

Minimum spanning network

A
  • Start with any vertex and delete its row
  • Select smallest entry from that column and label the new vertice as 2 and delete its row
  • Select smallest entry from any connected vertices’ columns and delete their rows until all finished
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How do you carry out Djikstra’s algorithm?

Shortest path from node to node

A
  • Starting node labelled as (1 0)
  • Write working values in all connected vertices (distance to starting node)
  • Select node with smallest working distance and repeat process until final node has a permanent label
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

CPA?

A
  • Forward pass - longest time
  • Backward pass - shortest time
How well did you know this?
1
Not at all
2
3
4
5
Perfectly