Weighted Directed Graph Implementation in Java & Bellman-Ford

Question

I am trying to figure out the best way to implement a Weighted Directed Graph in Java so to I can keep the running time on Bellman-Ford to |V|*|E|. Essentially my question is on how to represent the edges in the graph.

I have seen the use of an adjacency matrix, but I cannot seem to figure out how to use an adjacency matrix while at the same time keeping the running time below O(V^2). The reason I get V^2 as the running time is because Bellman-Ford requires that we loop through all edges, but it order to get a list of the edges I would need to loop through the entire matrix to get all edges. Is there anyway to get the list of edges faster than O(V^2) time with using an adjacency matrix?

Or do I need to use an adjacency list?

Answer 1

You can easily implement a class for Adjacency List. Following is the class which I use as an Adjacency List quite often which is easy to understand also. It maps an integer to a linked list.

class Adjacencylist {

    private Map<Integer, List<Integer>> adjacencyList;

    public Adjacencylist(int v){    //Constructor
        adjacencyList = new HashMap<Integer,List<Integer>>();
        for(int i=0;i<v;++i){
            adjacencyList.put(i, new LinkedList<Integer>());
        }
    }

    public void setEdge(int a,int b){    //method to add an edge
        List<Integer> edges=adjacencyList.get(a);
        edges.add(b);
    }

    public List<Integer> getEdge(int a){
        return adjacencyList.get(a);
    }

    public boolean contain(int a,int b){
        return adjacencyList.get(a).contains(b);
    }

    public int numofEdges(int a){
        return adjacencyList.get(a).size();
    }

    public void removeEdge(int a,int b){
        adjacencyList.get(a).remove(b);
    }

    public void removeVertex(int a){
        adjacencyList.get(a).clear();
    }

    public void addVertex(int a){
        adjacencyList.put(a, new LinkedList<Integer>());
    }
}

Before you complain that I need to implement a weighted graph, think about mapping a HashMap to an Integer. You can change the functions accordingly by replacing linked list with hash map. This saves you from O(n^2) time complexity.