Dynamic programming graph algorithm

Question

I am currently learning dynamic programming and i can't figure this problem out. Could someone give me an algorithm for it? : Consider a directed graph G = (V,E) where each edge is labeled with a character from an alphabet Sigma, and we designate a special vertex s as the start vertex, and another f as the final vertex. We say that G accepts a string A = a1a2 . . . an if there is a path from s to f of n edges whose labels spell the sequence A. Design an O((|V | + |E|)n) dynamic programming algorithm to determine whether or not A is accepted by G.

What have you tried so far? Can you explain us some of your reasoning for this problem? — BlackBear
– BlackBear, Commented Jun 20, 2014 at 10:49
Imagine you follow the first edge. What subproblem you then have to solve? — user189
– user189, Commented Jun 20, 2014 at 11:14
I am not following. You are basically describing an FSM (Finite State Machine / automaton). Note that you cannot really say if A is accepted or note without reading A, so the complexity will have to be (at least) O(S+V+E), where S is the length of A. — amit
– amit, Commented Jun 20, 2014 at 11:15
@user189 This problem does seem like a DP one but a backtracking one . In this case backtracking will give u solution in O(|E|*n) — Vikram Bhat
– Vikram Bhat, Commented Jun 20, 2014 at 11:26
@amit In case it is a deterministic FSM, a string will be accepted or rejected in O(S). In case the graph represents a non deterministic FSM, it can be transformed into a deterministic FSM once and then we are back to O(S). — Tarik
– Tarik, Commented Jun 20, 2014 at 11:51

Tarik · Accepted Answer · 2014-06-20 17:49:03Z

3

Let

first (str) return the first letter of str
Let len(str) return the length of str
Let rem(str) return str with the first character stripped off.

func (str, v1) =
    true if
    len(str)=0 and s == f
        or
    func(rem(str), v2) is true for any v2 such that there exists an edge connecting v1, v2 labeled first(str)

The values of f (str, v) can be memoised to avoid unnecessary recursive calls.

edited Jun 20, 2014 at 17:49

answered Jun 20, 2014 at 12:09

Tarik

11.2k2 gold badges31 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Apiwat Chantawibul Over a year ago

concise answer, but (1) where do you return false (2) the FSM is edge-labelled, so checking v2 == first(str) is a bit weird. maybe label(edge(v1,v2)) == first(str).

Apiwat Chantawibul Over a year ago

Sorry for the first remark, now I see where false value originate.

Tarik Over a year ago

@Billiska Thanks for your remark. For some reason, I thought that the vertices held the labels. Corrected my answer accordingly. As for being concise, I generally do not believe in spoon feeding, especially for what appears to be a students' homework.

Collectives™ on Stack Overflow

Dynamic programming graph algorithm

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related