1
\$\begingroup\$

A directed graph G is given with Vertices V and Edges E, representing train stations and unidirectional train routes respectively.

Trains of different train numbers move in between pairs of Vertices in a single direction.

Vertices of G are connected with one another through trains with allotted train numbers.

A hop is defined when a passenger needs to shift trains while moving through the graph. The passenger needs to shift trains only if the train-number changes.

Given two Vertices V1 and V2, how would one go about calculating the minimum number of hops needed to reach V2 starting from V1?


graph

In the above example, the minimum number of hops between Vertices 0 and 3 is 1.

There are two paths from 0 to 3, these are

0 -> 1 -> 2 -> 7-> 3

Hop Count 4

Hop Count is 4 as the passenger has to shift from Train A to B then C and B again.

and

0 -> 5 -> 6 -> 8 -> 7 -> 3

Hop Count 1

Hop Count is 1 as the passenger needs only one train route, B to get from Vertices 0 to 3

Thus the minimum hop count is 1.


Input Examples

Input Graph Creation

enter image description here

Input To be solved

enter image description here


Output Example

Output - Solved with Hop Counts

0 in the Hop Count column implies that the destination can't be reached

\$\endgroup\$
  • \$\begingroup\$ Hi, and welcome to the site! Questions here should be in the form of challenges with a winning criterion, such as code-golf. Could you add such a criterion, and also add an example input, such as one matching the picture? Thanks! \$\endgroup\$ – isaacg Mar 20 at 6:14
  • \$\begingroup\$ Thanks for the suggestions. I've edited the challenge to make the winning criteria based on algorithmic efficiency. I will shorty upload an example input. Thanks again! \$\endgroup\$ – Viswalahiri Mar 20 at 6:27
  • 5
    \$\begingroup\$ You also posted the same question on StackOverflow. Are you looking for programming help? \$\endgroup\$ – xnor Mar 20 at 7:03
  • 1
    \$\begingroup\$ How large can V, E and the number of trains be? \$\endgroup\$ – my pronoun is monicareinstate Mar 20 at 8:39
  • 1
    \$\begingroup\$ I took the liberty to edit the picture to add the missing train IDs. But feel free to rollback or edit further if necessary. \$\endgroup\$ – Arnauld Mar 20 at 9:14