Programming Geek
Rated 4.7/5 based on 1446 reviews

Single Source Shortest Path : Dijkstra's Algorithm

Given a graph G and a vertex v, find the shortest path to all reachable vertices from v.

For a given vertex, this algorithm find the shortest path to all the vertices if reachable from v of a directed graph. Graph must not contain a negative edge. This algorithm is used in routing . The image below illustrate the working of Dijkstra algorithm.

Dijkstra's algorithm. It picks the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors. (src:wikipedia)



Algorithm : 

  1. cost[n][n] is cost adjacency matrix with cost[i][j] set to a large number if there is no edge from i to j.
  2. Dist[n] holds distance of each vertex from source vertex and s[n] is set to false for each vertex.
  3. Initialize dist[i] to cost[v][i] and s[i]=0 for i=1 to n where v is the source vertex and cost[n][n] is cost adjacency matrix.
  4. s[v]=1; and dist[v]=0;
  5. for j=2 to n-1 do
    1. choose a vertex u nearest to v such that s[u]=0.
    2. s[u]=1;
    3. for each vertex w adjacent to u such that s[w]=0
      1. if dist[w]>dist[u]+cost[u][w] then
        1. dist[w]=dist[u]+cost[u][w]
  6. print dist[i] for  i=0 to n
The following java program shows the illustration of Dijkstra's algorithm to find shortest path . The problem statement is taken from coursera programming assignment #5 as:


Download the text file here. (Right click and save link as). 
The file contains an adjacency list representation of an undirected weighted graph with 200 vertices labeled 1 to 200. Each row consists of the node tuples that are adjacent to that particular vertex along with the length of that edge. For example, the 6th row has 6 as the first entry indicating that this row corresponds to the vertex labeled 6. The next entry of this row "141,8200" indicates that there is an edge between vertex 6 and vertex 141 that has length 8200. The rest of the pairs of this row indicate the other vertices adjacent to vertex 6 and the lengths of the corresponding edges.

Your task is to run Dijkstra's shortest-path algorithm on this graph, using 1 (the first vertex) as the source vertex, and to compute the shortest-path distances between 1 and every other vertex of the graph. If there is no path between a vertex v and vertex 1, we'll define the shortest-path distance between 1 and v to be 1000000. 

You should report the shortest-path distances to the following ten vertices, in order: 7,37,59,82,99,115,133,165,188,197. You should encode the distances as a comma-separated string of integers. So if you find that all ten of these vertices except 115 are at distance 1000 away from vertex 1 and 115 is 2000 distance away, then your answer should be 1000,1000,1000,1000,1000,2000,1000,1000,1000,1000. Remember the order of reporting DOES MATTER, and the string should be in the same order in which the above ten vertices are given.

JAVA implementation of Dijkstra's Algorithm :

import java.io.File;
import java.util.Scanner;

/**
 *
 * @author VIK VIKASH VIKASHVVERMA VIKKU
 * @website http://vikash-thiswillgoaway.blogspot.com
 */
public class Dijkstra {

    static int[][] cost;
    static int[] dist;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new File("./in.txt"));
        int n =200;
        cost = new int[n][n];
        dist = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    cost[i][j] = 0;
                } else {
                    cost[i][j] = 99999;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            String[] s = sc.nextLine().trim().split("\t");
            int v = Integer.parseInt(s[0]);
            for (int j = 1; j < s.length; j++) {
                String[] ls = s[j].split(",");
                cost[v - 1][Integer.parseInt(ls[0]) - 1] = Integer.parseInt(ls[1]);
            }
        }

           shortestPath(0,n);
     
        for (int i = 0; i < n; i++) {//7,37,59,82,99,115,133,165,188,197.
           
            switch (i + 1) {
                case 7: System.out.print(dist[i] + ",");
                    break;
                case 37: System.out.print(dist[i] + ",");
                    break;
                case 59: System.out.print(dist[i] + ",");
                    break;
                case 82: System.out.print(dist[i] + ",");
                    break;
                case 99: System.out.print(dist[i] + ",");
                    break;
                case 115: System.out.print(dist[i] + ",");
                    break;
                case 133: System.out.print(dist[i] + ",");
                    break;
                case 165: System.out.print(dist[i] + ",");
                    break;
                case 188: System.out.print(dist[i] + ",");
                    break;
                case 197: System.out.print(dist[i]);
                    break;



            }
        }


    }

    static void shortestPath(int v, int n) {
        int[] s = new int[n];
        for (int i = 0; i < n; i++) {
            s[i] = 0;
            dist[i] = cost[v][i];
        }
        s[v] = 1;
        dist[v] = 0;
        for (int i = 1; i < n - 1; i++) {
            int u = 0, dis = 0;
            for (int j = 0; j < s.length; j++) {
                if (s[j] == 0) {
                    dis = dist[j];
                    u = j;
                    for (int k = j + 1; k < s.length; k++) {

                        if (dis > dist[k] && s[k] == 0) {
                            dis = dist[k];
                            u = k;
                        }
                    }
                    break;
                }

            }
            s[u] = 1;
            for (int j = 1; j < n; j++) {
                if (s[j] == 0) {
                    if (dist[j] > (dist[u] + cost[u][j])) {
                        dist[j] = dist[u] + cost[u][j];

                    }
                }
            }
        }

    }
}
Have query? Drop a comment... :D

12 comments :

  1. I'm impressed about the description of the algorithm.
    the animated gif helps to get an idea of working - very nice.
    --
    graphs are very useful today. I'm just starting on working with them.
    Do you have a good technique to store them persistent (in a database)?

    ReplyDelete
  2. java Dijkstra
    Exception in thread "main" java.lang.NumberFormatException: For input string: "1
    80,982"
    at java.lang.NumberFormatException.forInputString(NumberFormatException.
    java:48)
    at java.lang.Integer.parseInt(Integer.java:458)
    at java.lang.Integer.parseInt(Integer.java:499)
    at Dijkstra.main(Dijkstra.java:25)

    Help me to clear this error

    ReplyDelete
    Replies
    1. @Rupavathy There was tab error in input file. I have rectified
      the input file. Now there is no problem... :)

      Delete
    2. Z:\3rd year\ADS>javac Dijkstra.java

      Z:\3rd year\ADS>java Dijkstra
      Exception in thread "main" java.io.FileNotFoundException: .\in.txt (The system c
      annot find the file specified)
      at java.io.FileInputStream.open(Native Method)
      at java.io.FileInputStream.(FileInputStream.java:138)
      at java.util.Scanner.(Scanner.java:656)
      at Dijkstra.main(Dijkstra.java:15)

      Z:\3rd year\ADS>

      Delete
  3. Replies
    1. @prakash click on the red colored "here" above to download the text file.

      Delete
  4. @sureddy Either you have not downloaded the text file or kept in.txt file in the same directory where your source file resides.

    ReplyDelete
  5. Hi, this exemple print the path (vertices visited) of the shortest road too ? If yes, where are you storing the vertices to print them later. I'm having problem with understanding how to print/compute the path. Thanks.

    ReplyDelete
    Replies
    1. @Dimofte Here I have printed only distance of shortest path and u can modify this algorithm to print the shortest path. I have not stored vertices here to print the shortest path as the problem statement was to print the shortest distance.

      Delete
  6. hello. i saw your writing and was very impressed.
    i have a little request about coding.

    let me introduce myself first.
    i'm a student learning datastructure and algorithm.
    i have little curiosity that how can i code dijkstra more useful.

    Your code was greatly operated.
    if it won't be bother you, can you tell me how to code or show me coding example
    about 'finding the shortest path from the single source to all the other vertices in G(V,E)

    here are some condition we must satisfy.

    1. V has 100 vertices
    (x, x^2 mod 100) where x=1,2, ...,100
    e.g. (1.1), (2,4), (3,9), ...(30,0), ...


    2. E is defined as
    if d<= 13 between v and w, then edge(v,w) exists
    if d> 13 between v and w, then edge(v,w) does not exists

    3. the start poin(single source) is (1,1)


    this is all that i want to add to your code.
    Again, i'm very impressed with your coding.
    that's why i ask help even thogh my request seems like rude.
    please help me if you could. and it would be nice let me know until Dec. 14.
    Thank you so much !

    ReplyDelete
    Replies
    1. @Jenny Perhaps your vertices indicate cartesian coordinate system and d represent the distance between two vertices. Let me know if I'm right.
      Although I have not written this blog to print path but You can solve this as follows...

      --> Transform all your vertices in simple form by giving them name like A, B, C etc.
      --> Make appropriate representation of graph viz. adjacency list or matrix. You will need two matrix, one containing distance between vertices and other containing name of vertices.
      --> Apply shortest path algorithm and update the second matrix at appropriate place e.g. at 100th line of code in above program.

      Delete