Shortest Path LinkedList

Question

I want to find the shortest path on a list of linked list, which represents a directed graph with cost per edge/path.

The output would look something like this, It tells me the cost it would take me to get from vertex 0 to the other vertices:

d[0 to 0] = 0
d[0 to 1] = 20
d[0 to 2] = 10

This is how I populate my list for testing.

LinkedList<GraphData> g = new LinkedList[3];

for (int i = 0; i < 3; i++)
    weight[i] = new LinkedList<GraphData>();

g[0].add(new GraphData(1, 20);
g[0].add(new GraphData(2, 10);

The GraphData class looks something like this:

int vertex, int edgeCost;

Now for my problem:

I want to find the shortest path from vertex v to all the others.

 public static int[] shortestPaths(int v, LinkedList<GraphData>[] cost)
{
    // get the set of vertices
    int n = cost.length;

    // dist[i] is the distance from v to i
    int[] dist = new int[n];

    // s[i] is true if there is a path from v to i
    boolean[] s = new boolean[n];

    // initialize dist
    for(int i = 0; i < n; i++)
        dist[i] = cost[v].get(i).getCost();

    s[v] = true;

    // determine n-1 paths from v 
    for ( int j = 2 ; j < n  ; j++ )
    {
        // choose u such that dist[u] is minimal for all w with s[w] = false
        // and dist[u] < INFINITY
        int u = -1;

        for (int k = 0; k < n; k++)
            if ( !s[k] && dist[k] < INFINITY)
                // check if u needs updating
                if ( u < 0 || dist[k] < dist[u])
                    u = k;
        if (u < 0)
            break; 

        // set s[u] to true and update the distances
        s[u]=true;

        for (int k = 0; k < n; k++)
            if ( !s[k] && cost[u].get(k).getCost() < INFINITY )
                if( dist[k] > dist[u] + cost[u].get(k).getCost())
                    dist[k] = dist[u] + cost[u].get(k).getCost();

        // at this point dist[k] is the smallest cost path from
        // v to k of length j.
    }       
    return dist;
}

This line dist[i] = cost[v].get(i).getCost(); throws "IndexOutOfBoundsException"

Any idea what I am doing wrong? Any help will be appreciated.

Answer 1

The problem is that your indices do not correspond. If you only put one distance, for instance

cost[0].add(new GraphData(5, 20));

then

cost[0].get(5).getCost();

will throw an IndexOutOfBoundsException, because you should do

cost[0].get(0).getCost();

in order to get 20 (which is very confusing).

I would advise using a Map, rather than a List to encode the edge costs.

You populate that Map like

List<Map<Integer, Integer>> g = new ArrayList<>();

for (int i = 0; i < 3; i++)
    g.add(new HashMap<Integer, Integer>());

g.get(0).put(1, 20);
g.get(0).put(2, 10);

With this, you could initialize your dist array like

// initialize dist
for(int i = 0; i < n; i++)
    dist[i] = cost.get(v).containsKey(i) ? cost.get(v).get(i) : INFINITY;

Answer 2

There are two common ways to represent graphs: adjacency lists and adjacency matrices.

Adjacency List: Array of lists. The element at index i is a small list containing the outgoing edges of vertex i. This is what you are creating when you populate the list.

Adjacency Matrix: Array of arrays, with cost[i][j] containing the cost of the edge from vertex i to vertex j. You are using the cost parameter as if it is an adjacency matrix.

You have two options:

• Change the graph construction to create an adjacency matrix and use an array of arrays
• Change the algorithm to treat cost as an adjacency list instead of an adjacency matrix

Here is the second option. I renamed a few things and simplified the initialization so that the first iteration calculates the distance to the immediate neighbours of v (as opposed to doing it as a special case at the start).

import java.util.*;

public class Main
{
    public static int[] shortestPaths(int v, LinkedList<Edge>[] edges)
    {
        // get the set of vertices
        int n = edges.length;

        // dist[i] is the distance from v to i
        int[] dist = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        // seen[i] is true if there is a path from v to i
        boolean[] seen = new boolean[n];

        dist[v] = 0;

        // determine n-1 paths from v
        for (int j = 0; j < n; j++) {
            // choose closest unseen vertex
            int u = -1;

            for (int k = 0; k < n; k++) {
                if (!seen[k]) {
                    // check if u needs updating
                    if (u < 0 || dist[k] < dist[u]) {
                        u = k;
                    }
                }
            }

            if (u < 0 || dist[u] == Integer.MAX_VALUE) {
                break;
            }

            // at this point dist[u] is the cost of the
            // shortest path from v to u

            // set seen[u] to true and update the distances
            seen[u] = true;

            for (Edge e : edges[u]) {
                int nbr = e.getTarget();
                int altDist = dist[u] + e.getCost();
                dist[nbr] = Math.min(dist[nbr], altDist);
            }
        }

        return dist;
    }

    public static void main(String[] args)
    {
        int n = 5;
        int start = 0;
        LinkedList<Edge>[] cost = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            cost[i] = new LinkedList<Edge>();
        }

        cost[0].add(new Edge(1, 20));
        cost[0].add(new Edge(2, 10));
        cost[1].add(new Edge(3, 5));
        cost[2].add(new Edge(1, 6));

        int[] d = shortestPaths(start, cost);
        for (int i = 0; i < n; i++) {
            System.out.print("d[" + start + " to " + i + "] = ");
            System.out.println(d[i]);
        }
    }
}

class Edge
{
    int target, cost;

    public Edge(int target, int cost) {
        this.target = target;
        this.cost = cost;
    }

    public int getTarget() {
        return target;
    }

    public int getCost() {
        return cost;
    }
}

Answer 3

Probably element cost[v].get(i) does not exist (no element with index i in this LinkedList which is cost[v]).

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html#get(int)