MarioYC's blog

¿How to handle shortest path with strings in the edges?
By MarioYC, 13 years ago, In English

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".

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
13 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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".

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it 
    4 3 1 4
1 2 a
1 3 b
1 4 c
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply