MarioYC's blog

¿How to handle shortest path with strings in the edges?
By MarioYC, 13 months 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 (9)
 
»
13 months 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 months 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 months 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 months 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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  •  
    »
    »
    13 months 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
    •  
      »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -35 Vote: I do not like it

      I gotta say am sooo lost. help me undastand better of u can reach me on www.portal.unn.edu.ng. thanks guys.

      → Reply