Graph Algorithms

Question 1

Dijkstra’s algorithm (3)

Answer 1

1. ) Used to find the shortest path from one node (“source”) to every other node.
2. ) Part of greedy technique.
3. ) Works only on graphs with non negative edges.

Question 2

Dijkstra’s how (6)

Answer 2

1. ) Assign 0 to initial node and infinity to all others.
2. ) Set initial node as current, all others as unvisited.
3. ) Calculate all tentative distances from adjacent nodes. If value is lower than current assign it.
4. ) Set node as visited.
5. ) if destination node is set as visited or no more nodes are available, algorithm has finished.
6. ) else select node with lowest tentative distance and repeat from 3.

Question 3

Spanning tree (1)

Answer 3

1.) Tree which contains all vertices in the graph.

Question 4

Minimum spanning tree (1)

Answer 4

1.) Spanning tree in a weighted graph with the lowest possible weight.

Question 5

Prim’s algorithm (2)

Answer 5

1. ) Used to find the minimum spanning tree in a graph.

2. ) Part of greedy technique.

Question 6

Prim’s how (3)

Answer 6

1. ) Select a vertex to be the first in the tree.
2. ) Consider all vertices adjacent to the tree, and add the lowest one.
3. ) Repeat 2 until each vertex is included.

Question 7

Kruskal’s algorithm (2)

Answer 7

1. ) Used to find the minimum spanning tree in a graph.

2. ) If graph is made of sub-graphs, find minimum spanning forest.

Question 8

Kruskal how (6)

Answer 8

1. ) Remove all loops.
2. ) Remove parallel edges (keep ones with lowest weight).
3. ) Create edge table sorted in ascending order.
4. ) Select edge with minimum weight.
5. ) Select edge with minimum weight which doesn’t form a cycle.
6. ) Repeat 5 until each vertex is included.