Question

Question 5: Say that we are given a directed graph with costs 1 or 2 on every edge and a vertex s. Give the fastest algorithm you can to find the distance from s to all the vertices in V − s.

Please explain the algorithm in words, not pseudocode. Thanks.

Answer 1

This problem can be solved using Dijkstra's Algorithm which helps us to find the shortest distance
from a given source vertex 's' to all the other vertices in the graph G, where the graph can be
directed or undirected.

Algorithm:-

1. Create an empty set "st" for the shortest path tree that will keep track of vertices included in it, i.e. whose minimum distance from the source is calculated already and finalized.

2. Then we will have to assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Then assign distance value as 0 for the source vertex so that it is picked first to calculate the minimum distance for other vertices.
3. We will run a loop while "st" set doesn’t include all vertices

---> Pick a vertex u which is not there in the "st" set and has minimum distance value.

---> Include u to "st" set.

---> Update the distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if the sum of the distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

Kindly Upvote the answer if it helps to solve your query and comment to ask if you have any queries regarding the solution or approach.