Dijkstra (Graph)

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class SearchAlgorithms {
    public static <T> void Dijkstra(Graph<T> graph, Vertex<T> source) {
        ArrayList<Vertex<T>> unfinishedVertices = new ArrayList<Vertex<T>>();
        for (Vertex<T> vertex : graph.Vertices()) {
            vertex.Distance = Integer.MAX_VALUE;
            vertex.Parent = null;
            unfinishedVertices.add(vertex);
        }
        source.Distance = 0;

        while (unfinishedVertices.size() > 0) {
            Vertex<T> vertex = GetClosestVertex(unfinishedVertices);
            unfinishedVertices.remove(vertex);
            for (Vertex<T> adjVertex : graph.GetAdjacentVertices(vertex)) {
                if (adjVertex.Distance > vertex.Distance + graph.GetEdgeWeight(vertex, adjVertex)) {
                    adjVertex.Distance = vertex.Distance + graph.GetEdgeWeight(vertex, adjVertex);
                    adjVertex.Parent = vertex;
                }
            }
        }
    }

    public static <T> ArrayList<Vertex<T>> DijkstraWithGoal(Graph<T> graph, Vertex<T> source, Vertex<T> goal) {
        if (source.equals(goal)) {
            ArrayList<Vertex<T>> tmp = new ArrayList<Vertex<T>>();
            tmp.add(source);
            return tmp;
        }
        ArrayList<Vertex<T>> unfinishedVertices = new ArrayList<Vertex<T>>();
        for (Vertex<T> vertex : graph.Vertices()) {
            vertex.Distance = Integer.MAX_VALUE;
            vertex.Parent = null;
            unfinishedVertices.add(vertex);
        }
        source.Distance = 0;

        while (unfinishedVertices.size() > 0) {
            Vertex<T> vertex = GetClosestVertex(unfinishedVertices);
            unfinishedVertices.remove(vertex);
            if (vertex.equals(goal)) {
                return GetPathToSource(vertex);
            }
            for (Vertex<T> adjVertex : graph.GetAdjacentVertices(vertex)) {
                if (adjVertex.Distance > vertex.Distance + graph.GetEdgeWeight(vertex, adjVertex)) {
                    adjVertex.Distance = vertex.Distance + graph.GetEdgeWeight(vertex, adjVertex);
                    adjVertex.Parent = vertex;
                }
            }
        }
        return null;
    }

    private static <T> Vertex<T> GetClosestVertex(ArrayList<Vertex<T>> list) {
        Vertex<T> candidate = list.get(0);
        for (Vertex<T> vertex : list) {
            if (vertex.Distance < candidate.Distance) {
                candidate = vertex;
            }
        }
        return candidate;
    }

    public static <T> ArrayList<Vertex<T>> GetPathToSource(Vertex<T> from) {
        ArrayList<Vertex<T>> path = new ArrayList<Vertex<T>>();
        Vertex<T> next = from;

        while (next != null) {
            path.add(next);
            next = next.Parent;
        }

        return path;
    }

}

import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {

        System.out.println("===========Dijkstra=============");

        Vertex<String> v1 = new Vertex<String>("v1");
        Vertex<String> v2 = new Vertex<String>("v2");
        Vertex<String> v3 = new Vertex<String>("v3");
        Vertex<String> v4 = new Vertex<String>("v4");
        Vertex<String> v5 = new Vertex<String>("v5");
        Vertex<String> v6 = new Vertex<String>("v6");

        ArrayList<Vertex<String>> vertices = new ArrayList<Vertex<String>>();
        vertices.add(v1);
        vertices.add(v2);
        vertices.add(v3);
        vertices.add(v4);
        vertices.add(v5);
        vertices.add(v6);

        Graph<String> graph = new Graph<String>(vertices);

        graph.CreateDirectedEdge(v1, v2, 5);
        graph.CreateDirectedEdge(v5, v1, 5);
        graph.CreateDirectedEdge(v5, v4, 1);
        graph.CreateDirectedEdge(v4, v3, 1);
        graph.CreateDirectedEdge(v2, v5, 2);
        graph.CreateDirectedEdge(v3, v2, 1);
        graph.CreateDirectedEdge(v4, v6, 2);
        graph.CreateDirectedEdge(v3, v6, 2);
        graph.CreateDirectedEdge(v6, v2, 3);

        System.out.println(graph.toString());

        //SearchAlgorithms.Dijkstra(graph, v4);

        ArrayList<Vertex<String>> path = SearchAlgorithms.DijkstraWithGoal(graph, v5, v2);
        System.out.println("Printing path from v5 to v2");
        Collections.reverse(path);
        for (Vertex<String> vertex : path) {
            System.out.println(vertex);
        }
    }
}

===========Dijkstra=============
Graph:
v1    Edge to: v2(w=5.0)
v2    Edge to: v5(w=2.0)
v3    Edge to: v2(w=1.0) v6(w=2.0)
v4    Edge to: v3(w=1.0) v6(w=2.0)
v5    Edge to: v1(w=5.0) v4(w=1.0)
v6    Edge to: v2(w=3.0)

Printing path from v5 to v2
{Vertex} v5
{Vertex} v4
{Vertex} v3
{Vertex} v2