Dijkstra’s algorithm in Java

Posted on by

Dijkstra’s algorithm, conceived by computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Find more here.

This is simple java implementation of Dijkstra’s algorithm.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
package myclass.Graphs;

import myclass.PrintArray;

/**
 *
 * @author Wijebandara
 */
public class DijkstrasAlgorithm
{
    private int data[][];
    private int d[];
    private int pi[];
    private boolean h[];

    public DijkstrasAlgorithm(int data[][])
    {
        this.data=new int[data.length][data.length];
        this.data=data;
        this.d=new int[data.length];
        this.pi=new int[data.length];
        h=new boolean[data.length];
    }
    public void DijkstrasAlgorithm(int s)
    {
        initialize();

        d[s]=0;
        pi[s]=0;
        h[s]=true;
        java.util.LinkedList<Node> q =new java.util.LinkedList<Node>();
        for(int i=0;i<data.length;i++)
        {
            if(data[s][i]!=0)
            {
                q.add(new Node(s,i,data[s][i]));
            }
        }       

        for(int i=0;i<data.length;i++)
        {
            if(data[s][i]!=0)
            {
                relaxation(s,i);
            }
        }

        while(q.size()!=0)
        {
            for(int i=q.size()-1;i>=0;i--)
            {
                for(int j=0;j<i;j++)
                {
                    if(q.get(j).w>q.get(j+1).w)
                    {
                        Node hold=new Node();
                        hold=q.remove(j);
                        q.add(j+1,hold);
                    }
                }
           }
            Node hold=q.removeFirst();
            for(int i=0;i<data.length;i++)
            {
                if(data[hold.v][i]!=0 && d[i]==-1)
                {
                    q.add(new Node(hold.v,i,data[hold.v][i]));
                }
            }
            for(int i=0;i<data.length;i++)
            {
                if(data[hold.v][i]!=0)
                {
                    relaxation(hold.v,i);
                }
            }
        }   
        PrintArray.printArray(d," ");
        System.out.println();
        PrintArray.printArray(pi," ");
        System.out.println();
    }

    private void initialize()
    {
        for(int i=0;i<data.length;i++)
        {
            d[i]=-1;
            pi[i]=-1;
            h[i]=false;
        }
    }

    private void relaxation(int u ,int v)
    {
        if(!h[v] || d[v]>d[u]+data[u][v])
        {
            d[v]=d[u]+data[u][v];
            pi[v]=u;
            h[v]=true;
        }
    }

    class Node
    {
        int u;
        int v;
        int w;
        Node(int u,int v,int w)
        {
            this.u=u;
            this.v=v;
            this.w=w;
        }
        Node(){}
    }
}

Hope you will enjoy…!

Leave a comment