Problem 7 A directed graph contains a cycle if it is possible to travel from one
ID: 3855494 • Letter: P
Question
Problem 7
A directed graph contains a cycle if it is possible to travel from one vertex back to itself. For example, the graph below contains a cycle because you can travel from A to B to C and back to A.
Following the pseudocode conventions of this course, give an algorithm to find the weight of the shortest cycle in a directed, weighted graph. The input to your algorithm is a graph G, represented in an adjacency list and source vertex s. It should return the weight of the shortest cycle in G.
Hint: You can run Dijkstra’s algorithm on your graph as a part of your solution.
Explanation / Answer
The algorithm is as follows-
It basically iterates through all the nodes of the graph and, for each of them, it iterates through the adjacent nodes, and checks first if the adjacent node w is the source node v, that would mean that u is connected back to the source node, creating a cycle.
The second expression - it basically is checking if the current min_weight is less than the distance of u plus the weight of the edge between u and w (the source node).