What are the best algorithms to compute an itinerary for a public transport app?

Question

I am creating an app for a public transports app, and I would need to compute itineraries.

However, I am not sure about what algorithm to use? A classic pathfinding algorithm like Dijkstra's or A*?

The fact that I have to handle both

1. basic pathfinding (stops to stops without walking)
2. advanced pathfinding (walking between stops)
3. harder combining both into one algorithm

makes me wonder what to choose precisely.

Thanks for helping 😀

Mods: Feel free to move the question to the appropriate place if my post isn't where it belongs

Answer 1

Dijkstra vs A* :

A* is faster to compute but can give wrong result, Dijkstra will find the shortest/fastest path all the time.

I'd use Dijkstra for that application.

pseudo-code :

class Path
{
    List<Node> nodesOfThePath;
    int length;
}

List<Path> paths = findAllLinksRelatedTo(startPoint); //You have to write a function to get the nodes linked to the given point
paths.Sort(); //sort using the length, ascending

while (paths.length > 0)
{
    if (paths[0].getLastestNode() == FinalPoint)
        return (paths[0]); //this is the shortest one

    List<Path> tempPaths = findAllLinksRelatedTo(paths[0].getLastestNode()); //get all nodes related to the lastest one of the shortest actual path or null if none was found
    paths.removeAt(0); //remove the shortest path
    foreach (tempPath in tempPaths)
        paths.Add(tempPath);
    paths.sort();
}
return (null); //no path found