### MarioYC's blog

By MarioYC19 months ago, ,

As the title says, in a graph where the distance of going between two nodes is the concatenation of the strings in the edges along the path between this two verticesm, and we want to find the lexicographically shortest distance, what distance function and which algorithm can we use to solve this kind of problems?

I was trying to solve this problem, and implement a code which uses the Floyd-Warshall algorithm, but there is a problem with cases like this:

V = 3, E = 3, s = 0, e = 2 0 -> 1 a 0 -> 1 ab 1 -> 2 c

The code returns "ac", but the right answear is "abc".

•
• +5
•

 » 19 months ago, # | ← Rev. 3 →   +5 1) For each node you can determine, if "gold node" is reachable from it. You can do it with 1 bfs with reversed edges from "gold node"2) Start from start node, always select smallest lexicographically edge leading to a vertex from which the “gold node” is reachable. (Thx for Endagorion) 3) If you find cycle, it's "NO".
•
 » » 19 months ago, # ^ | ← Rev. 2 →   +5 ``````4 3 1 4 1 2 a 1 3 b 1 4 c ``````
•
 » » » 19 months ago, # ^ |   0 I think you can discard nodes from which the gold node isn't reachable after doing the reversed bfs to avoid that case. And how to handle cases where an edge is prefix of another?
•
 » » » 19 months ago, # ^ |   0 In 2nd step you should choose edge u->v, only if from v you can reach "gold node". For this check we do 1st step with bfs from last node :)
•
 » » » » 19 months ago, # ^ |   0 In a case like4 4 0 3 0 1 ab 0 2 ab 1 3 c 2 3 dit can fail depending on which edge you choose.
•
 » » » » » 19 months ago, # ^ |   0 Ok, 1 sec, need to check.
•
 » » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Now I got AC at Aizu OJ (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1169) using Bellman Ford starting from the destiny node. This gives TLE in TJU OJ so there must be some faster method.EDIT: finishing the algorithm when finding a cycle reduced the time, AC now.
•
 » » 19 months ago, # ^ |   +5 2) needs to be like that: Start from start node, always select smallest lexicographically edge leading to a vertex from which the "gold node" is reachable.
•
 » » » 9 months ago, # ^ |   -35 I gotta say am sooo lost. help me undastand better of u can reach me on www.portal.unn.edu.ng. thanks guys.