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
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
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
4
Q
CPA?
A
- Forward pass - longest time
- Backward pass - shortest time