0

I'm projecting an algorithm to find a path in a public transport network, but I don't know how to make it simple, I'm thinking to this from yesterday. My objective is to find a path that minimize the bus changes, and other path that don't mind about bus changes, but they have to be short in time). This second algorithm is a k-shortest path algorithm (probably k = 3 or 4), for which I don't know any efficient implementation. I'd like to implement the two algorithms in C# and apply it to a real public transport network. Any hint? Excuse me for my very bad English, but I'm from Italy :)

litiales
  • 171
  • 4
  • 12

2 Answers2

3

A very common pathfinding algorithm is the A* search algorithm.

A lot of implementations in c# can be found, for example here on Codeguru or here on msdn.

You can find other ideas on this stackoverflow thread.

Maybe you should use that and ponderate bus changes or something like that.

Community
  • 1
  • 1
Bgi
  • 2,513
  • 13
  • 12
  • As upper, I already knew A* algorithm, but how can I modify it to give a weight to the bus changes? – litiales Sep 14 '12 at 15:03
  • It should be possible by defining the heuristic to be higher when changing bus, what do you think ? – Bgi Sep 14 '12 at 15:21
  • 1
    @litiales Define each path with two segments: 1) path length (i.e. distance or time), and 2) a connector path that represents transitioning onto that path where no transfer would have a weight of 0, but a transfer would have some weight. So the total path weight would be the sum of the two. – Tergiver Sep 14 '12 at 16:24
1

You could make use of Dijkstra's-Algorithm. Try here as a start.

http://www.codeproject.com/Articles/19919/Shortest-Path-Problem-Dijkstra-s-Algorithm

BarrieK
  • 1,239
  • 1
  • 10
  • 12
  • I already knew Dijkstra's algorithm but how can I modify that to reduce bus changes? It "easely" finds shortest path, without checking for bus changes. – litiales Sep 14 '12 at 15:03