CODEWITHSUNDEEP
algorithmgraph
AmirHosein Adavoudi
AmirHosein Adavoudi

Reputation: 117

Possibility of multiple shortest cycles in a directed and undirected graph

Is there any possibility that a weighted directed or undirected graph has more than one shortest cycle? I mean, the shortest cycles have the same total weights.

For example, in a shortest-directed cycle, let's say in both directions, the cycle has the same total weight. So, in this case, we have two shortest cycles. Am I right?

Upvotes: 0

Views: 30

Answers (1)

Berthur
Berthur

Reputation: 4495

Yes, a graph can have several shortest cycles. All you need to do is draw an example:

O --- 1
| \   |
|  \  |
|   \ |
2 --- 3

We can see that its shortest cycle has length 3. One such cycle is (0, 1, 3, 0) and another is (0, 3, 2, 0).

For directed simple graphs, you can find a similar trivial example. For weigthed graphs, remember that every unweighted graph is a weighted graph (with weigth 1 everywhere).

Upvotes: 1

Related Questions