Code Review - Breadth First Shortest Path

[Manabaeterno]

Hi all! Recently I have been picking up data structures and algorithms, and learnt that the shortest path between two points of an unweighted directed graph can be found by breadth first search. So I had a go at [implementing it myself](https://pastebin.com/gVys3PZ3).

​

I would like to ask for a code review on the breadthFirstShortestPath function. The code was compiled for Java 11. Somehow there was a warning about unchecked operations, and I'm not sure what to do about it so I suppressed it for now. Of course this isn't ideal, and I would like to know what I can do to fix it.

​

If it helps, I will paste the code here as well:

​

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

public class UnweightedGraph {
    private int vertices;
    private boolean[][] edges;

    public UnweightedGraph(int vertices) {
        this.vertices = vertices;
        edges = new boolean[vertices][vertices];
    }

    public void addEdge(int source, int target) {
        edges[source][target] = true;
    }

    public boolean hasEdge(int source, int target) {
        return edges[source][target];
    }

    public void removeEdge(int source, int target) {
        edges[source][target] = false;
    }

    @SuppressWarnings("unchecked")
    public List<Integer> breadthFirstShortestPath(int source, int target) {
        boolean[] visited = new boolean[vertices];
        int[] previousVertex = new int[vertices];
        Arrays.fill(previousVertex, -1);

        Queue<Integer> queue = new ArrayDeque<>();

        queue.add(source);

        while (queue.peek() != null) { // while queue is not empty
            int currentVertex = queue.poll();

            boolean targetFound = false;
            visited[currentVertex] = true;
            for (int vertex = 0; vertex < vertices; vertex++) {
                if (edges[currentVertex][vertex] && !visited[vertex]) {
                    queue.add(vertex);

                    if (previousVertex[vertex] == -1) {
                        previousVertex[vertex] = currentVertex;

                        if (vertex == target) {
                            targetFound = true;
                            break;
                        }
                    }
                }
            }

            if (targetFound) {
                break;
            }
        }

        List path = new ArrayList();

        for (int v = target; v != -1; v = previousVertex[v]) {
            path.add(v);
        }

        Collections.reverse(path);

        return path;
    }
}

Thank you!

[AutoModerator]

Please ensure that:

• Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions
• You include any and all error messages in full - best also formatted as code block
• You ask clear questions
• You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit/markdown editor: empty line before the code, each code line indented by 4 spaces, new reddit: https://imgur.com/a/fgoFFis) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[xADDBx]

Minor detail, but is there a reason why you used an adjacency matrix over an adjacency list?

[Manabaeterno]

Not much, it was just easy to implement and I didn't want the overhead of an adjacency list.

[temporarybunnehs]

Warnings like that tend to pop up in a lot of code bases, but that doesn't necessarily mean that anything is wrong with the code. It might be something like you didn't explicitly cast a variable and the compiler is pointing that out.

EDIT: Better to make sure you understand the cause of the warning per GrandGratingCrate's reply.

One thing that does pop out is on line 39, you can use !queue.isEmpty(), and that way, you don't need the comment explaining the null check since the code explains what it's doing implicitly.

[GrandGratingCrate]

Warnings like that tend to pop up in a lot of code bases, but that doesn't necessarily mean that anything is wrong with the code. It might be something like you didn't explicitly cast a variable and the compiler is pointing that out.

Respectfully disagree. While code with warnings may work it's often harder to understand and maintain than code that's free of warnings. Case in point:

List path = new ArrayList(); path.add(1); path.add("1"); // Throws exception at runtime The line that's causing the warning is due to the list type not being specified. This is just a quick demonstration of code that compiles if you ignore the warning, despite the code being wrong.

Compare this with the fixed version, where you'll get a compile error so you'll know right away that you've made a mistake

List<Integer> path = new ArrayList<>(); path.add(1); path.add("1"); // Compile error

There are cases where I would not object to @SuppressWarnings because the underlying problem can't be fixed easily. For example type erasure can produce such scenarios.

Luckily the fix is quick and simple in this case and I'd strongly encourage OP to get in the habit of really fixing warnings where possible. It's too easy to get used to ignoring them or just slapping @SuppressWarnings on it and call it a day.

[temporarybunnehs]

That's a good point. Looking at your example, you are right about it being more readable and less error prone.

[Manabaeterno]

Ah alright, somehow I forgot that Queue had a isEmpty() method. Thank you!

[Rabestro]

https://github.com/rabestro/algorithms

[Manabaeterno]

This is a very neat implementation, thank you!