CODEWITHSUNDEEP
c++loops
Khalid
Khalid

Reputation: 303

Find indirect train connections

I have to find train journeys between two given city codes, if there is no direct route then I should find an indirect route via other journeys. If I want to go from A to B, I might have to go from A to C to B.

My file for the train routes is of form: departure code destination code company price time This looks at direct routes, between two city codes.

Now I've used the following loop for direct connections, and it works, I just need help with the indirect connections.

// load file data into v1

string dep, dest;
cout << "\n\tEnter the departure: ";
cin >> dep;
cout << "\n\tEnter the destination: ";
cin >> dest;

for(int i = 0; i < v1.size(); ++i) {
    // Departure() and Destination(), return the departure/destination codes
    if (v1[i].Departure() == dep && v1[i].Destination() == dest)
          // here I find all the direct routes
    else
         // indirect routes dealt with here
}

I think for indirect routes, I have to in the else part deal with them. But I'm struggling to see how I would do it, I think I have to look at the where the first departure's destination and match this with my given dest.

Upvotes: 2

Views: 870

Answers (3)

user2313067
user2313067

Reputation: 603

You could take a look at what Google has done for Google Transit in Google Maps: http://ad.informatik.uni-freiburg.de/files/transferpatterns.pdf.

Upvotes: 1

Escualo
Escualo

Reputation: 42082

I recommend that you read the following essay (it is very short):

http://www.python.org/doc/essays/graphs.html

It is written by Guido von Rossum, the creator of the Python programming language.

I like it because it discusses how to implement graphs using dictionaries (std::map, in C++ parlance), and provides very short, effective implementations of find_path, find_all_paths, and find_shortest_path. Given that they are implemented in Python, translating them to C++ is straightforward (because Python is easy to read; consider it pseudocode rather than the Python solution).

For example, the following code implements find_all_paths:

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths

Notice that it is a recursive implementation.

Upvotes: 2

MarZab
MarZab

Reputation: 2623

What you have there, is a graph.

There are many ways to find a path, many to find the shortest path and many to find the cheapest path.

This is not a simple else statement but I would recommend you reading up these:

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

http://en.wikipedia.org/wiki/Shortest_path_problem

Upvotes: 5

Related Questions