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

Improve this question
\$\endgroup\$
8
  • \$\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\$ Commented Mar 20, 2020 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\$ Commented Mar 20, 2020 at 6:27
  • 5
    \$\begingroup\$ You also posted the same question on StackOverflow. Are you looking for programming help? \$\endgroup\$ Commented Mar 20, 2020 at 7:03
  • 1
    \$\begingroup\$ How large can V, E and the number of trains be? \$\endgroup\$ Commented Mar 20, 2020 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\$ Commented Mar 20, 2020 at 9:14

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.