L15-16 (BFS, Dijkstra, Bellman Ford)

Question 1

The ______ of a path is given by the number of edges on the path, whereas the ______ between two vertices in a graph is the length of the shortest path between them

Answer 1

length
distance

Question 2

Which algorithm do we use to find the shortest paths from a starting vertex to every reachable vertex, if every edge has equal cost?

Answer 2

BFS (Breadth First Search)

Question 3

What data structure do we use in a BFS (Breadth First Search) algorithm?

Answer 3

FIFO queue

Question 4

What is the runtime for BFS?

Answer 4

O(V + E)
V - the number of vertices (nodes)
E - the number of edges

Question 5

The runtime for Djiksta’s is ________ with using an array, ________ with using a binary-tree, and ________ with using a fibonacci heap

Answer 5

O(V^2)
O((V+E)logV)
O(V*logV + E)

Question 6

Define the Bellman-Ford algorithm

Answer 6

The Bellman-Ford algorithm is a dynamic programming-based method used to find the shortest path from a single source vertex to all other vertices in a weighted, directed graph. It is capable of handling graphs with negative weight edges and can detect negative weight cycles, which distinguishes it from Dijkstra’s algorithm.

Question 7

Define a Negative weight cycle. Whats special about Bellman-Ford vs Djikstra?

Answer 7

A cycle in a graph where the sum of the edge weights is negative. Bellman-Ford can detect such cycles, which makes it more versatile than Dijkstra’s algorithm.

Question 8

What’s the time complexity of Bellman-Ford?

Answer 8

The time complexity of the Bellman-Ford algorithm is O(|V| * |E|), where |V| is the number of vertices and |E| is the number of edges in the graph.

Question 9

Describe the Bellman-Ford algorithm step-by-step

Answer 9

1. Initialization: Set the distance to the source vertex as 0 and distances to all other vertices as infinity.
2. Edge Relaxation: Repeat for |V| - 1 iterations, where |V| is the number of vertices in the graph:
   a. For each edge (u, v) with weight w(u, v), compare the current shortest path distance to vertex v (dist[v]) with the candidate path distance (dist[u] + w(u, v)).
   b. If the candidate path distance is smaller, update dist[v] to the new value.
3. Negative Cycle Detection: Try to relax all edges one more time. If any distance is updated, a negative weight cycle exists in the graph.

Question 10

Describe the Relaxation process for Bellman-Ford

Answer 10

Compare the current shortest path distance from the source vertex to another vertex with a new candidate path distance that includes an additional edge. If the new candidate path distance is shorter, the current shortest path distance is updated to the new value, potentially improving the solution.

Question 11

What is the time complexity of the Bellman-Ford algorithm

Answer 11

The Bellman-Ford algorithm has a time complexity of O(|V| * |E|), where |V| is the number of vertices and |E| is the number of edges in the graph. This is because the algorithm iterates over all edges in the graph |V| - 1 times during the edge relaxation step, and one more time for negative cycle detection.

Question 12

Define Dijkstra’s algorithm

Answer 12

Dijkstra’s algorithm is a graph search algorithm that finds the shortest path from a single source vertex to all other vertices in a weighted, directed graph with non-negative edge weights. It is a greedy algorithm that iteratively selects the vertex with the smallest known distance from the source and updates the distances of its neighbors.

Question 13

What’s a requirement/assumption for Djikstra’s algorithm for it to work?

Answer 13

Dijkstra’s algorithm assumes that all edge weights in the graph are non-negative. This constraint is necessary for the algorithm’s correctness, as negative edge weights can lead to incorrect shortest path calculations. In contrast, the Bellman-Ford algorithm can handle graphs with negative edge weights and detect negative weight cycles.

Question 14

What are the detailed steps of djikstra’s algorithm?

Answer 14

1. Initialization: Set the distance to the source vertex as 0 and distances to all other vertices as infinity. Create an empty set of visited vertices and a priority queue with all vertices, sorted by their distances from the source.
2. Iterative Vertex Selection:
   a. Select the vertex (u) with the smallest distance that has not been visited yet and mark it as visited.
   b. For each neighbor (v) of u, calculate the tentative distance (dist[u] + w(u, v)) and compare it with the current distance (dist[v]).
   c. If the tentative distance is smaller, update dist[v] and update the priority queue.
   d. Repeat steps 2a-2c until all vertices have been visited or the priority queue is empty.

Question 15

Is Djikstra’s algorithm greedy? does it find the optimal solution?

Answer 15

Dijkstra’s algorithm is a greedy algorithm because it iteratively selects the vertex with the smallest known distance from the source without considering the global structure of the graph. However, due to its non-negative edge weight constraint, Dijkstra’s algorithm is guaranteed to find the globally optimal solution (shortest paths) by iteratively exploring vertices in non-decreasing order of their distances from the source.

Question 16

In Dijkstra’s algorithm, will the distance mapping of a vertex ever underestimate the true distance to a vertex?

Answer 16

No, dist(x) will always give an overestimate (or the actual distance) to the true distance to x

Question 17

Give the greedy algorithm to find the single source shortest path in a weighted DAG (Directed Acyclic Graph)? Is it guaranteed to give optimal solution for all verticies?

What’s the time complexity ?

Answer 17

1. In dist[], set all distances to infinity, except for the source node, set it to 0
2. Topologically sort the graph using DFS (which takes O(V+E) time)
3. For each vertex v in the topological order, perform the following steps:
   a. For each neighboring vertex u of v with edge weight l(v, u):
   i. Calculate the tentative distance (dist[v] + l(v, u)) and compare it with the current distance (dist[u]).
   ii. If the tentative distance is smaller, update dist[u] with the new value.

After these steps, the dist[] array will contain the shortest path distances from the source vertex to all other vertices in the graph. The time complexity of this is O(V+E)

This algorithm does not guarantee an optimal solution because there may be paths which are not considered because of the selection greedy nature