Algorithms for bidirectional graphs

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.

Also, some of the nodes are one-way only.

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)?

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?

---an example---

              3
  A --<2/3>-- B --<3/2>-- C
  | 1        2|3
  |           |
  ^1/4       ^4/3
  |           |
  |3         4|
8 D --<3/5>-- E
  |2
  |
1 ^3/1
  |
  |
  F

Where <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.

Hope that makes sense...

Simon

(p.s apologies for bad terminology - "links", "edges" - whatever you like ;) )

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开发者_JAVA百科 how far away the platform is, how regular the service is, etc).

Yes, treat these as two edges instead of one. Then you can use traditional graph theory algorithms on this without a problem, especially if you are always guaranteed to have weights in each direction. These algorithms are easy to find if you are just using a 'normal' graph like I have just helped you create.

You can use Dijkstra's for shortest path.

You can Prim's for a minimum spanning tree.

You can Google for the asymmetric TSP to try and find an algorithm for that, and I'm pretty sure the Introduction to Algorithms has something on this too. Sorry I couldn't find a good implementation of that one for you. There are also a couple of good questions on here about the asymmetric TSP, now that you know it's called the asymmetric TSP.

Good luck! I love graph theory.

-Brian J. Stinar-

For your "interchange" weights, you can make a little subgraph to encode those. For example, you have:

  |   
  |3  
8 D --
  |2
  |

You can encode that using just weights on edges, like this:

  |
  |
  D0
  | \3
  |  \
 8|   D2--
  |  /
  | /2
  D1
  |
  |

Just watch out for the fact that you don't have to use the 8 edge to get from D0 to D1, as you can go D0->D2->D1 for a weight of 5 instead. I'm not sure if that is allowed in your original formulation.