<![CDATA[CodeGuru Forums - Algorithms & Data Structures]]>
http://forums.codeguru.com/
enThu, 24 May 2018 12:05:55 GMTvBulletin60http://forums.codeguru.com/images/misc/rss.png<![CDATA[CodeGuru Forums - Algorithms & Data Structures]]>
http://forums.codeguru.com/
Shortest path problem
http://forums.codeguru.com/showthread.php?561495-Shortest-path-problem&goto=newpost
Sat, 28 Apr 2018 23:45:17 GMT paths(map > 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.]]>miamiacodehttp://forums.codeguru.com/showthread.php?561495-Shortest-path-problem