CODEWITHSUNDEEP
javagraphdijkstrashortest-path
user1301404
user1301404

Reputation:

Dijkstra shortest path for an undirected graph

My following code is working perfectly fine for directed graphs and when given an undirected graph, it will not return the shortest path.

public void Djikstra(int s){
    boolean[] marked = new boolean[V];
    dist = new double[V];

    for(int i = 0; i<V; i++){ # initializing array
        dist[i] = Double.POSITIVE_INFINITY;
    }
    dist[s] = 0.0;

    Queue<Integer> pqs = new PriorityQueue<Integer>();

    pqs.add(s);
    while(!pqs.isEmpty()){
        int v = pqs.poll();

        if(marked[v]) continue;
        marked[v] = true;

        for(Edge e : get_list(v)){ # get_list(v) will return an iterable from the adjacency list at index v 
            v = e.getV()
            int w = e.getW();
            if(dist[w] > dist[v] + e.getWeight()){
                dist[w] = dist[v] + e.getWeight();
                distances[w] = e #all the distances will be stored in this array
                pqs.add(w);
            }
        }
    }
}

I'm not sure what's my mistake over here? I'm kind of sure it's a simple error, some hints will do the job.

Thanks.

Edit:

public void addEdge(Edge e){
    adj[e.getV()].add(e);
    adj[e.getW()].add(e);
}

Upvotes: 0

Views: 5992

Answers (2)

Fabio Cassinelli
Fabio Cassinelli

Reputation: 47

You have to add two different edges, the direct and the inverse. Change

public void addEdge(Edge e){
    adj[e.getV()].add(e);
    adj[e.getW()].add(e);
}

in

public void addEdge(Edge e){
    adj[e.getV()].add(e);
}

and, when you add the edges, do it like this:

Edge e = new Edge(from, to, weight);
Edge f = new Edge(to, from, weight);

addEdge(e);
addEdge(f);

Upvotes: 0

quazzieclodo
quazzieclodo

Reputation: 831

Consider the differences between a directed path from node 1 to 2 and an undirected path from node 1 to 2.

What would you need to add to the directed graph (which your algorithm can solve) to make it equivalent to the undirected graph?

EDIT:

Figured it out, I think. Here's the hint: You are currently changing resetting v inside of your for loop. This will not cause an error with a directed graph, but what happens if the edge is listed as going from w to v instead of v to w undirected?

EDIT2:

Something like this:

First, remove v = e.getV();

Second, change the next line to int w = (v == e.getV()) ? e.getW() : e.getV();

This sets the value of w to whichever vertex of your edge v is NOT.

This second suggestion is equivalent to the following (maybe a bit easier to read):

int w = e.getW();
if (w == v) {
    w = e.getV();
}

Upvotes: 2

Related Questions