Re: [jgrapht-users] pathfinding: edge weight dependent on path-taken-so-far

[Robert F. <fle...@gm...>]

Hi Rushang,

Thanks for your quick response! Maybe the traffic analogy isn't the best
one.

More to the point: a SPCO/SPTT electrical switch such as
https://en.wikipedia.org/wiki/Switch#/media/File:SPDT-Switch.svg

I'm representing this switch as two edges: one connecting L1 to COM and one
connecting L2 to COM. Both of those edges are available for path traversal,
but the switch can't be in both positions simultaneously. I.e., the switch
cannot not allow L1 to connect to L2.

I was thinking of somehow using edge weights dynamically, such that if an
algorithm uses the L1-COM edge, then the L2-COM edge would have a very high
weight.

What do you think?

Thanks,
Robert

On Fri, Jul 24, 2015 at 1:19 PM, Rushang Karia <rus...@ho...>
wrote:

> I guess this classifies as an online algorithm. As for mutually exclusive
> events, they mean independent events, I do not see how you are relating it
> to edge weights in a shortest path scenario? Could you please explain it so
> that I can be sure of my assumption?
>
>
>
> And to answer your question, you will need to implement an online
> algorithm for the shortest path that changes the graph as data of each
> vertex (stoplight) changes. Is this something what you wanted to achieve?
>
>
>
> Lets suppose you have a graph A-B-C where A-B-C and A-C. Further A-B = 1,
> A-C = 10, B-C=2. Obviously the shortest path is A-B-C from A to C. But lets
> suppose that when you were inspecting distances at point B, a stoplight
> turned on and now B-C = 100 because of the stoplight. Then the new shortest
> path is A-C at that point in time? But this means you need to backtrack all
> the way back to the source node.
>
>
>
> Let me know if my assumption of your problem is correct?
>
>
>
> *From:* Robert Fleming [mailto:fle...@gm...]
> *Sent:* Friday, July 24, 2015 12:15 PM
> *To:* jgr...@li...
> *Subject:* [jgrapht-users] pathfinding: edge weight dependent on
> path-taken-so-far
>
>
>
> Sorry if this has already been asked/answered on the list.
>
>
>
> When finding the shortest path between two vertices in a directed graph,
> is there any way for the weight of an edge to be dependent on which other
> edges are in the path? E.g. as a way to implement mutually exclusive edges.
>
>
>
> Example: an intersection of two roads, controlled by stoplights. At any
> given moment, traffic is allowed through in one direction. *Because* of
> that, the other paths through that intersection are unavailable (i.e. very
> high weight).
>
>
>
> Thanks!
>
> Robert
>