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…!

Breadth-first search in Java

Posted on by

In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations:

  1. Visit and inspect a node of a graph;
  2. Gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes.

Find more here.

This is simple java implementation of Breadth-first search.

 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
 
package myclass.Graphs;

import myclass.PrintArray;

/**
 *
 * @author wijebandara
 */
public class BreadthFirstSearch
{
    private int [][] data;
    private int [] d;
    private int [] pi;
    private int [] state;

    BreadthFirstSearch(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];
        this.state=new int [data.length];

    }
    public void breadthFirstSearch(int s)
    {

        java.util.LinkedList<Integer>  q=new java.util.LinkedList<Integer>();
        for(int i=0;i<data.length;i++)
        {
            state[i]=-1;
            d[i]=0;
        }
        q.add(s);
        state[s]=0;

        while(q.size()!=0)
        {
            int hold= q.removeFirst();

            for(int i=0;i<data.length;i++)
            {
                if(data[hold][i]!=0 && state[i]==-1)
                {
                    q.add(i);
                    state[i]=0;
                    d[i]=d[hold]+1;
                    pi[i]=hold;
                }
            }
            state[hold]=1;
        }
        PrintArray.printArray(d," ");
    }
    public boolean isPathBetween(int u,int v)
    {
        breadthFirstSearch(u);
        if(d[v]!=0)
        {
            return true;
        }
        return false;
    }

}

Hope you will enjoy…!

Bellman–Ford algorithm in Java

Posted on by

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

Find more here.

This is simple java implementation of Bellman–Ford 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
 
package myclass.Graphs;

import myclass.PrintArray;

/**
 *
 * @author wijebandara
 */
public class BellmanFord 
{
    private int data[][];
    private int d[];
    private int pi[];
    private boolean h[];
    
    BellmanFord(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 boolean bellmanFord(int s)
    {
        initialize();
        d[s]=0;
        pi[s]=0;
        for(int i=0;i<data.length;i++)
        {
            for(int u=0;u<data.length;u++)
            {
                for(int v=0;v<data.length;v++)
                {
                    if(data[u][v]!=0)
                    {
                        relaxation(u,v);
                    }
                }
            }
        }
        PrintArray.printArray(d," ");
        System.out.println();
        PrintArray.printArray(pi," ");
        System.out.println();
        for(int u=0;u<data.length;u++)
        {
            for(int v=0;v<data.length;v++)
            {
                if(data[u][v]!=0 && d[v]>d[u]+data[u][v])
                {
                    System.out.println(v+" "+u);
                    return false;
                }
            }
        }
        return true;
    }
    
    private void initialize()
    {
        for(int i=0;i<data.length;i++)
        {
            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;
        }
    }

}

Hope you will enjoy…!