Path between two cities using BFS in java

Question

I am trying to make a data structure for storing Map contents like roads and cities information. I am using linkedlist of vertices/cities and when a vertex/city is created it creates another linkedlist of edges in its constructor. I need an algorithm to find a shortest path between two random cities. My modified BFS algo is not working absolute fine . ALgorithm:

public void getPath(String from, String to) {
        Queue<cVertex> Q = new LinkedList<cVertex>();
        List<cVertex> visited = new LinkedList<cVertex>();
        cVertex l = null;
        for (int i = 0; i < c.size(); i++) {
            if (c.get(i).cityName.equals(to)) {
                l = c.get(i);
                break;
            }
        }
        for (cVertex a : c) {
            if (a.cityName.equals(from)) {
                // System.out.println(a.cityName);
                Q.add(a);
                System.out.println("\nPath from " + a.cityName + " to "
                        + l.cityName);
                break;
            }
        }
        while (!Q.isEmpty()) {
            cVertex u = Q.remove();
            System.out.print(u.cityName);
            if (u.cityName.equals(l.cityName)) {
                return;
            }
            System.out.print("-->");
            visited.add(u);
            for (cVertex w : c) {
                for (Edge e : w.list) {
                    Edge n = e;
                    for (cVertex d : c) {
                        if (d.cityName.equals(e.to)) {
                            if (!visited.contains(d) && !Q.contains(d))
                                Q.add(d);
                        }
                    }
                }
            }
        }
    }

I need help! e.to means to is the cityName with which this edge is connected.

Answer 1

You should say in your question that "c" is static variable, and that it is an array of cVertex. Also show declarations and definitions of all classes you are using in the getPath function, like: fields, properties and methods of cVertex and Edge classes also in your question.

I want also you to explain me how possible in Java to implicitly convert LinkedList to Queue and LinkedList to List. I just want to know. I am interested, because in C# all these classes exist in System.Collections.Generic namespace, but you cannot neither implicitly nor explicitly convert LinkedList to neither Queue nor List.

For C#:

Queue<cVertex> Q = new LinkedList<cVertex>();
List<cVertex> visited = new LinkedList<cVertex>();

This writing is forbidden and makes errors, even if the class cVertex was declared and defined somewhere.

But anyway your question is awesome and challenging.

Unfortunately, I have never learnt Java, so I can not post you my code that might be incorrect in terms of syntax and grammar, but still I understood your smart question and still I can help you, so I will just tell you my idea and what you have to do in order to answer your question.

First of all delete or at least exclude from your project the cVertex and the Edge classes that you are using inside getPath function, and add a new class. Call this class by name "City". Instances of this class should store the name of the city as string, and an array of type City. In this array, refer all cities that you can go from this City by one road, or one bus or even walking.

The next step is to create instances of the City class until you have created all the cities of the country on the territory and store them all in one array. If you like to call this array "c", then you are allowed. Of course that I understand that this is very important that this array is static, so you will be able to use it in many other functions.

Now you need a function that receives one parameter of string, which is a name of a city and it returns from the static array a reference to an instance of City with that name.

This is very simple to implement this function. You just for loop (go through) all the cities and check if the name of the current city in the for loop matches the string parameter. If yes, then return the reference of the current city in the for loop and the function stops automatically. If a city was not found with this name, then the function returns null of course.

You can call this function by name "findCityByName".

When you are done with this function, the next step is to rename the function getPath from "getPath" to "getPaths" (just add to end the 's' letter), and change the return type of this function from void to Boolean. This change is good, because the return value of this function will inform you if the function has either succeed or failed. The function fails and returns false if input parameters are invalid. Otherwrise the function succeeds and returns true.

Now add three additional very necessary parameters in order to make this function working and successful.

Still the first two parameters of this function are two names of two cities that you want to go from to as strings like you posted in your question, but the third parameter should be list of type City. This list stores references to all cities that were visited. You can call this parameter by name "visited". Your mistake was to define "visited" as local variable, instead of parameter.

The fourth parameter should also be a list, but of type array of type City. Every array in this list stores only references to all cities that you must go first, before you reach the target city from the city you go out. Every array in this list is actually a path. This list contains only all possible paths to reach the target city from the "from" city, that their names specified in the first two parameters of this function as strings. This list actually contains what you expect to get from this function.

You can call this parameter by name "paths".

The fifth last parameter should be also a list of type City like the type of the third parameter - "visited", but this list stores references to cities that were visited, but not to all not like in the "visited" list parameter. This is the difference between the "visited" list parameter to this parameter. Every time a call to getPaths function ends, the last element of this list is removed, not like in "visited" list parameter. "visited" list only adds references of cities to itself. It never removes them, but the list in the last parameter does.

You can call this parameter by different name "currentPath".

Note that you must recall this function more than once inside this function in order for this to work!

This function must be recursive!

These are all the parameters of this function, but this is very important always to pass the last three additional parameters (3rd, 4th and 5th) as references, and not as copies!!!

The function won't work for sure, if you pass these parameters as copies.

Now finally let's start rewrite the implementation code of this function.

In the beginning, call the "findCityByName" function twice to get the cities used to find all the possible paths between them. If one of them or both is/are null, then return false to stop the function immediately, because you cannot calculate path between two cities that one of them doesn't exist or both! Also the function fails, because one of the first two parameters or both is/are invalid!

If both is not null, so both cities exist, then you can start for loop all the cities in the array of the "from" city that you can go to.

If the current city in the for loop is the target city you want to go, then allocate a new array in the size of "currentPath" list and copy all references from the "currentPath" list to this array and then add it to the "paths" list and return true to stop the current function immediately, because a path was found, and also parameters are valid for the current getPath function.

Else (if the current city in the for loop is not the target city then) add to both lists "visited" and "currentPath" the reference of the current city in the for loop and recall getPaths function and input in the first parameter the name of the current city in the for loop. In the 2nd, 3rd, 4th and 5th parameters input the 2nd, 3rd, 4th and 5th parameters of the current getPaths function called respectively (pick from the title). still don't forget to pass the 3rd, 4th and 5nd parameters as references and not as copies or function won't work!

All what I told you to do in the else statement is happens only if the "visited" list doesn't already contain reference to the current city in the for loop! Otherwise for loop continues to next City. It is important to check that first.

At last (after the for loop) if "currentPath" is not empty, then remove the last reference only from "currentPath" and not from "visited" too!!!

Then return true. The first two parameters of the first call to getPaths function are valid. Function may succeed.

This is all declaration, definition and the implementation of the getPaths function.

Note that everytime before you call this function, you must allocate memory for the three lists that this function gets in the last three parameters. Before you pass these lists by reference to this function, assign them by empty constructor, or constructor with no parameters, or constructor that initializes the new list empty at first. This is very important in the first call to getPaths functions that all lists the last three parameters are empty.

When the first call to getPaths function ends and the function succeed, then only "currentPath" will remain empty. Otherwise only "visited" will not remain empty. In case that the function succeed, and at least one path was found, then "paths" will be filled with data. Only "paths" is interesting, not the two others, because it is the answer given by getPaths function.

After that list of paths is ready, now you need to convert it to a jugged array of City by allocating a new array in the size of this list and just copy from that list all references to this array.

Jugged array is an array that it's type is also array.

Now let's define a new function: getShortestPath

This function receives only one parameter of jugged array of City, and returns an array of City.

Actually it receives paths and returns the shortest path. Algorithm to implement this function is very simple.

First define new local variable: name "minSize" and type int and assign it to the size of the first array in the jugged array.

Then define another new local variable: name "shortestPath" and type 'array of City' and set it to the reference of the first array in the jugged array.

Then for loop the rest arrays (start from the second array to the last) and if the size of the current array is smaller than the value of "minSize", then set both "minSize" to the size of the current array in the for loop and "shortestPath" to the reference of the current array in the for loop.

At last, after for loop, return "shortestPath".

If you have many cities, and getPaths works too much time, so you can add placement to the City class (X and Y coordinates as doubles).

Then delete or comment getShortestPath function, and rename the function getPaths from "getPaths" to "getShortestPath", and delete or comment the "paths" parameter and all code that relate to this parameter. Also change the name of the parameter "currentPath" to "path" and apply this change to all occurrences in the function.

Also add another AND condition in the if statement that is the else statement in the for loop. In the additional condition check that the current city in the for loop is closest to the target city. To know that you need first before the for loop to add another for loop to all cities in the "from" array, calculate and add the distances of all these cities to the target city into new local list of doubles that you allocate before. Then declare, define and implement a function that returns the smallest double in a list of doubles. Then call this function to get the distance of the closest city to the target city and keep it in a new local variable: name "min" and type double

In the additional condition, if the calculated distance of the current city to the target city approximately equals to the value of "min", then the current city is the closest city to the target city.

Also define, declare and implement a new function that receive two parameters of City and returns the distance between them as double, and use this function to help you.

The math expression that calculates distance of two points is:

sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)) or sqrt((x2 - x1)^2 + (y2 - y1)^2)

pow(a, b) = a^b, pow(n, 2) = n^2

Also in the getShortestPath function (that once was called by name "getPaths") delete or comment all lines that remove elements from "path" (that once was called by name "currentPath")

The new allocated list path is empty, before getShortestPath function call, but after call and after you pass it by reference, "path" is filled in data. It should be the shortest path between the "from" city to the "to" city.

Post a comment and tell me if you also know C# too, not only Java.

I know C#, so if you tell me yes, then I will post the code in C#.

That is all. I hope this answers your question. Try this idea and post a comment to tell me if it was helpful.

GOOD LUCK from me! :D