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".
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".
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?
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 :)
In a case like
4 4 0 3 0 1 ab 0 2 ab 1 3 c 2 3 d
it can fail depending on which edge you choose.
Ok, 1 sec, need to check.
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.
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.