Week 7 - Dijkstra's Algorithm

Question 1

What is a weighted graph?

Answer 1

A weighted graph is a graph in which each edge has an associated numerical value (weight) that represents the cost, distance, or capacity of the connection between two nodes.

Question 2

What are some of the practical applications for weighted graphs?

Answer 2

Weighted graphs can be used in:
1. Navigation and Mapping
2. Network Routing
3. Project Planning
4. Social Networks
5. Supply Chain and Logistics
6. Bioinformatics

Question 3

What is an approach you can use for representing a weighted graph in Python?

Answer 3

You can represent a weighted graph in Python using two parallel dictionaries: one for the adjacency list and another for edge weights. You can also create a dictionary of dictionaries!

Question 4

What is Dijkstra’s Algorithm and how does it function?

Answer 4

Dijkstra’s algorithm finds the shortest path from a starting node to all other nodes in a weighted graph with non-negative edge weights. It iteratively selects the node with the smallest tentative distance, updates the distances of its neighbors, and continues until the shortest path to all nodes is determined.

Question 5

What are the steps involved in Dijkstra’s Algorithm?

Answer 5

Dijkstra’s Algorithm:

Initialize: Set the start node distance to 0 and others to infinity. Mark all nodes as unvisited and add them to a priority queue.

Select Node: Pick the unvisited node with the smallest distance.

Update Distances: Update the distances to its neighbors if a shorter path is found.

Mark as Visited: Mark the node as visited.

Repeat: Continue until all nodes are visited or the smallest distance in the queue is infinity.

Question 6

What is the single-source shortest path problem?

Answer 6

The single-source shortest path problem involves finding the shortest paths from a given starting node to all other reachable nodes in a weighted graph, ensuring each node is reached via the path with the lowest possible cost.

Question 7

What is the time complexity of Dijkstra’s algorithm?

Answer 7

Initialising the node costs takes O(V).

Finding the node with the next smallest cost takes O(V).

Overall, we have O(2V + V^2) which is just O(V^2).

Question 8

What are the limitation of Dijkstra’s algorithm?

Answer 8

The limitations of Dijkstra’s algorithm are:

1. It does not work for weighted graphs with negative edge weights.
2. It does not handle weighted graphs with negative cycles.