
April 28th, 2018, 06:45 PM
#1
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.

April 29th, 2018, 05:41 AM
#2
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.1)

April 29th, 2018, 03:22 PM
#3
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

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
