shortest track

[corbu]

hi all
i have a problem and i have no idea of how to start.
there is a graph direct with weight in R and a set of lines S. a track is considered "strained " related with S if any line (uv) are
either in S or there is no outgoing line from u in set s . (
the algorithm should answer if there exist a short track between all "strained " track related to S.

not sure if i understand it. maybe is something that is know. so please if you know or understand more give me a helpfull hint

[corbu]

the corect text is


i have a problem and i have no idea of how to start.
there is a graph direct with weights that are real and a set of arcs F. A track is named "strained " related to F
if any arc (uv) from track is either in F
or there is no outgoing arc from u in set F.
given 2 vertexes source and target (s,t) the algorithm should find the shortest path (s->t) from the strained paths relative to F
maybe is something that is well know.
so please if you know or understand more give me a helpfull hint

[mf]

there is a graph direct

You mean "a directed graph", right? And your term "track" means simply a path in the graph?

A [path] is named "strained " relat[ive] to F if any arc (uv) from [the path] is either in F
or there is no outgoing arc from u in set F.

I'm a bit confused by this definition. Do you mean "each arc" instead of "any arc"?

If yes, then how about simply removing all edges (u, v) such that (u,v) is not in F, and there is an edge (u, w) in F for some vertex w. After that you can use any standard shortest path algorithm (such as Bellman-Ford) to find the shortest path between s and t.

[corbu]

thank you so much for the time you took to look into the
term of the problem and to draw the solution.
sorry for my bad translation . It thought that arcs , tracks are part of the math heritage.
it seems that is not.
after i consulted with other big brains and i read more carefully the problem it resume to something like:
if we colour a bunch of edges with RED (the F set of edges)
the shortest path is restricted to a condition
iF there is a red edge (or possibly more ) then the path must leave along that red edge (or one of those red edges).
we can not have a red edge outgoing from u and for the path to NOT take that red edge.
is like a limit on what edges can take from any given node. ie not all edges are allowed. we are only allowed to travel along a sub-graph and need to solve your shortest path problem in that sub-graph.
thanks again.

do u think this algorithm will work:
remove the forbidden edge (edges that we are not allowed to take)
and calculate the shortest path into it.

[mf]

do u think this algorithm will work:
remove the forbidden edge (edges that we are not allowed to take)
and calculate the shortest path into it.

Yes, why wouldn't it work? By deleting these edges, 1) we're not changing the set of "good" paths (so, can't possibly miss an existing "good" path), and 2) every path remaining in the graph after this transformation is "good" (so, algorithm won't produce a "bad" path).

It thought that arcs , tracks are part of the math heritage.

I've never heard the term "track".
But "arc" is pretty common, though now most people seem to prefer the term "edge" instead.