none
How to get the shortest path between point from and to that are on the same metro line? RRS feed

  • Question

  • I have a point from and to on the same train/metro line and need to find the shortest path between those points. Each point has values (x,y) and I have a unit test that defines the rules for finding the path. I have three tests from which only T2(test two) is verified by my function but Test 1(T1 path_to_where_i_am)and Test 3 (T3 get_path_to_station_on_same_line) do not pass as I have problem to identify the steps and then translate them to the code.
    Function GetShortestPath
    public IReadOnlyList<IStation> GetShortestPath(IStation from, IStation to)
    {
        //T2 _cant_get_path_from_and_or_to_null()
        if (from == null || to == null || from == to) 
            throw new ArgumentException();
        //T1 _path_to_where_i_am()
        //s is added and then only one should be same as s
                
        //T3 get_path_to_station_on_same_line()
        // from to have to be on same line
        throw new NotImplementedException();
        //return pathBetweenFromTo;
    }
    Unit Test
    [Test1]
    public void T1_path_to_where_i_am()
    {
        ICity c = CityFactory.CreateCity("Paris");
        IStation s = c.AddStation("Opera", 0, 0);
        c.GetShortestPath(s, s).Single().Should().BeSameAs(s);
    }
    [Test2]
    public void T2_cant_get_path_from_and_or_to_null()
    {
        ICity c = CityFactory.CreateCity("Paris");
        IStation s = c.AddStation("Opera", 0, 0);
        Action action = (() => c.GetShortestPath(s, null));
        action.ShouldThrow<ArgumentException>();
        action = (() => c.GetShortestPath(null, s));
        action.ShouldThrow<ArgumentException>();
        action = (() => c.GetShortestPath(null, null));
        action.ShouldThrow<ArgumentException>();
    }
    [Test3]
    public void T3_get_path_to_station_on_same_line()
    {
        ICity c = CityFactory.CreateCity("Paris");
        IStation s1 = c.AddStation("Opera", 0, 0);
        IStation s2 = c.AddStation("Chatelet", 10, 10);
        IStation s3 = c.AddStation("Gare de Lyon", 20, 20);
        ILine l = c.AddLine("RER A");
        l.AddBefore(s1);
        l.AddBefore(s2);
        l.AddBefore(s3);
        var path = c.GetShortestPath(s1, s2);
        path.Count.Should().Be(2);
        (path[0] == s1 && path[1] == s2).Should().BeTrue();
        path = c.GetShortestPath(s2, s1);
        (path.Count == 2).Should().BeTrue();
        (path[0] == s2 && path[1] == s1).Should().BeTrue();
        path = c.GetShortestPath(s1, s3);
        (path.Count == 3).Should().BeTrue();
        (path[0] == s1 && path[1] == s2 && path[2] == s3).Should().BeTrue();
        path = c.GetShortestPath(s3, s1);
        (path.Count == 3).Should().BeTrue();
        (path[0] == s3 && path[1] == s2 && path[2] == s1).Should().BeTrue();
        path = c.GetShortestPath(s2, s3);
        (path.Count == 2).Should().BeTrue();
        (path[0] == s2 && path[1] == s3).Should().BeTrue();
    }

    Wednesday, January 22, 2020 11:25 AM

All replies

  • What exactly is your question?

    Do you want to start over? I have seen the A* or AStar algorithm used.

    https://en.wikipedia.org/wiki/A*_search_algorithm

    Did you write the code you show? Is it a known find shortest path method  or did you write the code?

    What exactly is it you don't understand?

    Is this for school?

    Wednesday, January 22, 2020 12:01 PM
  • Hi BarbraFleg, 

    Thank you for posting here.

    According to your description, I have some questions to confirm with you.

    Did you use  NUnit Test to test your application?

    Could you provide some related code about ‘ICity’, ‘IStation’ and ‘CityFactory’ ? It will help us to analyze your problem and make a test.

    We are waiting for your update.

    Best Regards,

    Xingyu Zhao


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    Thursday, January 23, 2020 7:25 AM
    Moderator
  • What is going on here?  You asked this exact question a week or two ago, and several of us have very patiently explained to you how to implement these functions.  Based on what I saw, you had already implemented most of them.  Now, all of a sudden, you have nothing??

    It's really not our job to do your homework.  You need to make a good faith attempt to write your own code.  Then show us what you have, and we can offer hints.

    And seriously, if you can't write the code for T1, then you are really in no position to be writing programs.  It could not possibly be any easier.


    Tim Roberts | Driver MVP Emeritus | Providenza &amp; Boekelheide, Inc.

    Thursday, January 23, 2020 7:40 AM