title: Algorithms for bidirectional graphs
body: <p>Say I have a graph (network) of nodes, with weightings on the following:
  1. travelling one way on a link between two nodes.
  2. travelling the other way on a link between two nodes (these might be different).
  3. changing from one link to another.</p>
  
  <p>Also, some of the nodes are one-way only.</p>
  
  <p>In this case, what would be the best algorithms for:
  a) finding a minimum spanning tree
  b) finding the shortest route between two nodes
  c) finding the "travelling salesman" path (i.e. the shortest route that goes everywhere, with minimum duplication)?</p>
  
  <p>Also, would it be best to treat the bi-directional thing as two single-directional paths, rather than a bidirectional path with different weightings in each direction?</p>
  
  <p>---an example---</p>
  
  <pre><code>              3
    A --&lt;2/3&gt;-- B --&lt;3/2&gt;-- C
    | 1        2|3
    |           |
    ^1/4       ^4/3
    |           |
    |3         4|
  8 D --&lt;3/5&gt;-- E
    |2
    |
  1 ^3/1
    |
    |
    F
  </code></pre>
  
  <p>Where &lt;2/3> means weight of 2 travelling left and 3 travelling right.
  ^1/4 means 1 travelling up and 4 travelling down. A single number between two links is the cost of changing links - e.g to go from AD to DF costs 8, and from AB to BE costs 2.</p>
  
  <p>Hope that makes sense...</p>
  
  <p>Simon</p>
  
  <p>(p.s apologies for bad terminology - "links", "edges" - whatever you like ;) )</p>
  
  <hr>
  
  <p>To try and explain the types of weighting better, imagine the edges are train tracks, and the nodes are stations. The cost on the edge is the journey time on a train between two stations, and the costs on the nodes are how long the interchange time is (which may vary between edges even at the same node, depending on how far away the platform is, how regular the service is, etc).</p>