Question

Implement Dijkstra's algorithm to find the shortest path from vertex O to all other vertices in the graph below. Use the adjacency list representation to store and use the graph in memory. Do not use any other representation Use vertex 'A' as your source vertex (begin the algorithm from A). Your output should be of the following format with the second column filled out. The distance from the source vertex (second column) is the sum of weights on the shortest path from the source vertex (A) to the particular vertex: Vertex Distance from source vertex m oo - I

Answer 1

Considering the adjacency list representation using java which involves multiple classes in a package. PriorityQueue is used in this algorithm

Edge.java // represents edge with weight

package temp;

public class Edge implements Comparable{
    private int startPoint;
    private int endPoint;
    private float weight;

    public Edge(int startPoint, int endPoint, float weight) {
        this.startPoint = startPoint;
        this.endPoint = endPoint;
        this.weight = weight;
    }

    public boolean equals(Edge other) {
        if (this.startPoint == other.startPoint) {
            if (this.endPoint == other.endPoint) {
                return true;
            }
        }
        return false;
    }
    
    public int compareTo(Object o) {
        Edge other = (Edge) o;
        return Double.compare(this.weight, other.weight);
    }

}

Graph.java //executes operation of adding,removing edges

package temp;

import java.util.Iterator;
import java.util.PriorityQueue;

public class Graph {
    private int vCount;
    private PriorityQueue<Edge>[] adj;

    public int getvCount() {
        return vCount;
    }

    public Graph(int vCount) {
        this.vCount = vCount;
        // initialize adj
        adj = new PriorityQueue[vCount];
        for (int i = 0; i < vCount; i++) {
            adj[i] = new PriorityQueue<Edge>();
        }
    }

    public void addEdge(int i, int j, float weight) {
        adj[i].add(new Edge(i, j, weight));
    }

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

    public void removeEdge(int i, int j) {
        Iterator<Edge> it = adj[i].iterator();
        Edge other = new Edge(i, j, 0);
        while (it.hasNext()) {
            if (it.next().equals(other)) {
                it.remove();
                return;
            }
        }
    }

    public PriorityQueue<Edge> neighbours(int vertex) {
        return adj[vertex];
    }

    public void printGraph() {
        for (int i = 0; i < vCount; i++) {
            PriorityQueue<Edge> edges = neighbours(i);
            Iterator<Edge> it = edges.iterator();
            System.out.print(i + ": ");
            for (int j = 0; j < edges.size(); j++) {
                System.out.print(it.next() + " ");
            }
            System.out.println();
        }
    }
}

Vertex.java

package temp;

public class Vertex implements Comparable{
    private int id;
    private float distance;
    private Vertex parent;
    
    public Vertex(){
        distance = Float.MAX_VALUE; // "infinity"
        parent = null;    
    }
    
    public Vertex(int id){
        this.id = id;
        distance = Float.MAX_VALUE; // "infinity"
        parent = null;    
    }

    public float getDistance() {
        return distance;
    }
    
    public void setDistance(float distance) {
        this.distance = distance;
    }
    
    public Vertex getParent() {
        return parent;
    }
    
    public void setParent(Vertex parent){
        this.parent = parent;
    }
    
    public int compareTo(Object o) {
        Vertex other = (Vertex) o;
        return Double.compare(this.distance, other.distance);
    }
}

TestGraph.java

package temp;

import java.util.Iterator;
import java.util.PriorityQueue;

public class TestGraphs {

    public static void main(String[] args) {
        Graph g = new Graph(5);
        
        System.out.println("Graph:");
        // add Edges
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
        
        // print Graph
        g.printGraph();

        // Dijkstra Shortest Path Algorithm
        System.out.println("Dijkstra Shortest Path:");
        Dijkstra(g, 0);
    }

    public static void Dijkstra(Graph g, int startVertex) {
        // for storing distances after removing vertex from Queue
        float[] distances = new float[g.getvCount()];
        // for storing father id's after removing vertex from Queue
        int[] parents = new int[g.getvCount()];
        for (int i = 0; i < g.getvCount(); i++) {
            parents[i] = -1;
        }

        // set up vertex queue
        PriorityQueue<Vertex> Q = new PriorityQueue<Vertex>();
        for (int i = 0; i < g.getvCount(); i++) {
            if (i != startVertex) {
                Q.add(new Vertex(i));
            }
        }

        // add startVertex
        Vertex node = new Vertex(startVertex);
        node.setDistance(0);
        Q.add(node);

        // loop through all vertices
        while (!Q.isEmpty()) {
            // get vertex with shortest distance
            Vertex u = Q.remove();
            distances[u.id] = u.getDistance();

            // iterate through all neighbours
            Iterator<Edge> it = g.neighbours(u.id).iterator();
            while (it.hasNext()) {
                Edge e = it.next();
                Iterator<Vertex> it2 = Q.iterator();
                while (it2.hasNext()) {
                    Vertex v = it2.next();
                    // check if vertex was visited already
                    if (e.endPoint != v.id) {
                        continue;
                    }
                    // check distance
                    if (v.getDistance() > u.getDistance() + e.weight) {
                        v.setDistance(u.getDistance() + e.weight);
                        v.setParent(u);
                        parents[v.id] = v.getParent().id;
                    }
                }
            }

        }
        
        // print final shortest paths
        System.out.println("Vertex\tDistance");
        for (int i = 0; i < g.getvCount(); i++) {
            System.out.println(i + "\t" + distances[i] );
        }

    }
}