Questions Tagged With shortesthttp://www.or-exchange.com/tags/shortest/?type=rssquestions tagged <span class="tag">shortest</span>enTue, 21 Jun 2016 16:05:15 -0400Shortest Path With Limitations on Node Visitationhttp://www.or-exchange.com/questions/13961/shortest-path-with-limitations-on-node-visitation<p>Hello,</p>
<p>I have a variant on the classic 'shortest path' problem and I don't know how to approach it. My graph topology is as such:</p>
<p>There is one source and one sink.</p>
<p>Other nodes are designated by a letter and subscript integer (e.g., A1,B1,C1,A2,B2,C2,....A30,B30,C30). There is one node per possible letter/integer combination.</p>
<p>There is one zero-cost directed edge from the source to each of A1, B1, C1. There is one zero-cost directed edge from each of the nodes with the largest integer to the sink (e.g., when the integers go up to 30, there is one zero-cost directed edge from A30 to the 'Final Destination Node', and an identical edge from B30 and from C30).</p>
<p>From each node there is a directed, weighted edge to one other node of each of the other letters with a larger integer.</p>
<p>For example, there may be a directed weighted edge from A1 to B3 and from A1 to C10; however you won't see edges from A1 to both B3 and B5 because the destinations are both 'B' edges.<br>
</p>
<p>There are no edges that move from one node with a letter, to another node with a letter (e.g., no B3 to B10) and no edges that move from a node with a higher integer to one with a lower integer (e.g., no B30 to C10).</p>
<p>I know that I can use Djikstra's algorithm to find a singular shortest path from origin to destination, but my goal is somewhat different. I want to:</p>
<p>1) Find a single shortest path from source to sink that visits each of the 'letters' once and only once. Any group of integers will work as long as I visit all the letters. Eg. visiting the node set A1, B22, and C27 between the source and sink is acceptable; visiting A10, A15, B22 is not.
2) Find two paths that, combined, visit each of the letters once and only once. If the 'letter set' was ABCDEF, one route could visit ABD and the other CEF; but we couldn't have one route visit ABCD and the other visit DEF, because D would overlap. The goal is to identify two paths that find the minimal longer route - I don't care about the total time as much as about this minimax.
3) Same question as #2 but with 3 paths, 4 paths, etc.</p>
<p>I assume I could make a very complicated integer program but didn't know if there were shortest-path algorithms already available to solve this. Bonus points if it's ready-made in an R package.</p>
<p>Thanks in advance for any help you can provide.</p>
<p>Ralph</p>kmwestTue, 21 Jun 2016 16:05:15 -0400http://www.or-exchange.com/questions/13961/shortest-path-with-limitations-on-node-visitationoptimizationshortestFind shortest path that uses exactly one arc in a subsethttp://www.or-exchange.com/questions/7516/find-shortest-path-that-uses-exactly-one-arc-in-a-subset<p>Let G(N,A) be a graph with nodes set N and arcs set A.</p>
<p>Problem: find the shortest path from node i to node j such that the path contains exactly one arc from the set $A', which is a subset of A.</p>
<p>I am guessing this is a well-known problem. Can someone point me to a reference? Thanks!</p>Hugh MedalThu, 28 Feb 2013 21:50:59 -0500http://www.or-exchange.com/questions/7516/find-shortest-path-that-uses-exactly-one-arc-in-a-subsetoptimizationshortestreferenceReduced cost for edges in shortest path algorithmhttp://www.or-exchange.com/questions/7184/reduced-cost-for-edges-in-shortest-path-algorithm<p>Hi everybody</p>
<p>When using primal simplex algorithm to find shortest O-D path on an undirected graph (with non-negative costs) it is possible to extract the reduce cost of every node(source, sink and any intermediate node) in the course of algorithm. </p>
<p>If for a given O-D, in addition to the original shortest path model constraints:</p>
<p>Min \(\sum_{i,j} c_{ij}x_{ij}\)
s.t. </p>
<p>\(\sum_j x_{oj} = 1\)</p>
<p>\(\sum_i x_{id} = 1\)</p>
<p>\(\sum_{i:\neq k} x_{ik} = \sum_{i\neq k} x_{ki}~~\forall k\)</p>
<p>we also have </p>
<p>\(x_{ij} \leq 1\) for some \(i,j\)
and
\(x_{ij} \leq 0\) for some other \(i,j\)</p>
<p>then is there any variant of shortest path algorithms, e.g. Dijkstra or simplex, primal dual etc, that also let us extract the reduced costs corresponding to edges? as the dual has multiple optimal solutions, what are the possibilities to chose solution which produce dual values both for edges and nodes?</p>
<p>I appreciate any constructive comment</p>
<p>regards,
Shahin</p>ShahinGSat, 05 Jan 2013 09:24:36 -0500http://www.or-exchange.com/questions/7184/reduced-cost-for-edges-in-shortest-path-algorithmpathcostreducedshortest