dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: Shortest path problem

  1. #1
    Join Date
    Apr 2018
    Posts
    2

    Post Shortest path problem

    Hello,
    I need help with following function:

    Write function with prototype map<char,string> paths(map<char,set<char> > g, char s) which does the following:
    - g is directed graph: v is element of g[u] iff there is edge from u to v
    - g doesn't have to be defined on all vertices of a graph: if it is not defined on a vertex a, it's considered that g[a]={}
    - return value has to be map with shortest paths from s to other vertices (which can be accesed from vertex s) considering directions
    - if path from a to f is through vertices b and c respectively, path shoud be represented with string „bcf“
    - if s is not vertex in a given graph (it is not in the domain of g nor is a value of any element in domain of g), function should return an empty map
    - if s is a vertex in a given graph but there is no edge from it to any vertex, function should return map containing only pair (s, ““)
    - graph can have cycles and loops - be aware od that
    - example: given graph g is: g['a']={'b'}, g['b']={'c','d'}, g['d']={'a','d'}, g['e']={'d'}, g['f']={} then
    paths (g,a) should return map {('a',""), ('b',"b"), ('c',"bc"), ('d',"bd")}
    paths(g,b) should return map {('a',“da“),('b',),('c',c),('d',d)}
    paths(g,c) should return map {('c',)}
    paths(g,d) should return map {('a',“a“),('b',“ab“),('c',“abc“),('d',)}
    paths(g,e) should return map {('a',“da“),('b',“dab“),('c',“dabc“),('d',“d“),('e',)}
    paths(g,f) should return map {('f',)}

    I tried writting a recusion and also some BFS algorithms and nothing seems to be working. So I would really appreciate if someone could help me in detail.
    Thanks.

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,486

    Re: Shortest path problem

    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2017 (15.8.9)

  3. #3
    Join Date
    Apr 2018
    Posts
    2

    Re: Shortest path problem

    Not really but thanks anyway

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)