CODEWITHSUNDEEP
javaalgorithmdijkstra
leonz
leonz

Reputation: 1127

Why doesn't Dijkstra's algorithm work as it should for given graph?

I have the following code, Dijkstra's algorithm, that I made using Wikipedia's article on the algorithm.

For the given graph (see image) and starting node (1), it returns 5 as distance to node (4), which is obviously false. However, when going from node (4), it returns 4 as distance to (1), which is correct. What is wrong in my code?

Graph

//source = starting point, adj[] = adjacency list
private static int dijkstra (int source, ArrayList<Road>[] adj) {
    HashSet<Integer> vertices = new HashSet<>();

    int[] dist = new int[adj.length];
    int[] prev = new int[adj.length];

    for (int i = 0; i < adj.length; i++) {
        dist[i] = Integer.MAX_VALUE;
        prev[i] = Integer.MAX_VALUE;
        vertices.add(i);
    }

    dist[source] = 0;

    while (!vertices.isEmpty()) {
        int current = Integer.MAX_VALUE;
        for (int v: vertices) {
            if (dist[v] < current) {
                current = v;
            }
        }
        vertices.remove(current);

        for (Road v: adj[current]) {
            int alt = dist[current] + v.distance;

            if (alt < dist[v.end]) {
                dist[v.end] = alt;
                prev[v.end] = current;
            }
        }
    }
}

class Road {
    int end;
    int distance;
}

//This loop builds adjacency list from input such as "1 3 2", where 1 represents
// starting node, 3 represents end node and 2 represents weight of that edge.
//start and end values are decremented in order to be 0-indexed

for (int i = 0; i < M; i++) {
    int start = in.nextInt() - 1;
    int end = in.nextInt() - 1 ;
    int dist = in.nextInt();

    adj[start].add(new Road(end, dist));
    adj[end].add(new Road(start, dist));
}

Upvotes: 2

Views: 490

Answers (1)

user4668606
user4668606

Reputation:

This piece of code is causing the error:

int current = Integer.MAX_VALUE;
for (int v: vertices) {
    if (dist[v] < current) {
        current = v;
    }
}

I assume it's supposed to search the unvisited node that has the shortest path from the start-vertex. But this should look rather like this:

int currentPathLen = Integer.MAX_VALUE, current = -1;
for (int v: vertices) {
    if (dist[v] < currentPathLen) {
        current = v;
        currentPathLen = dist[current];
    }
}

Upvotes: 2

Related Questions