What's wrong with this code (Dijkstra Shortest Path algorithm)

Posted on 2008-11-20
Last Modified: 2012-05-05
I want to calculate the shortest path length using Dijkstra's algorithm. But somehow I made a mistake, but I cannot figure it out

Below is my code.
I use adjacency matrix to represent graph so I wrote my own code for the linked list.

I ran some sample data and it was okay. But the checking system says that I was wrong...

Thank you for your help!


public class List {

	private static int MAX = Integer.MAX_VALUE;


	private class Point {

		int p, len;

		Point next;


		public Point(int x, int y){

			p = x;

			len = y;

			next = null;



	private Point head;

	private Point tail;


	public List(){

		head = null;

		tail = null;




	//Add edge with vertex x and length len

	public void add(int x, int len){

		Point p = new Point(x, len);


		if (head == null){

			head = tail = p;


		else{ = p;

			tail = p;




	//Get edge of vertex y

	public int get(int y){

		if (head == null)

			return MAX;

		Point id = head;

		while (id != null){

			if (id.p == y)

				return id.len;

			id =;


		return MAX;



	//Remove the edge of vertex x

	public int remove(int x){

		if (head == null)

			return MAX;

		Point id = head;

		if (head.p == x)


			int val = head.len;

			head =;

			return val;


		while ( != null)


			if ( == x)


				int val =; =;

				return val;


			id =;



		return MAX;




// MAX = Integer.MAX_VALUE to denote infinity

//The List[] data = new List[n] stores the adjacency lists for n vertices

public static int shortestPath(List[] data, int n, int src, int dest){

		Vector<Integer> t = new Vector<Integer>();	//Tenative set


		int [] val = new int[n];	//Value of the shortest paths from src to other vertices


		//Initial value for val[i] is the length between src and node i

		for(int i = 0; i < n; i++){

			val[i] =  (i == src)? 0 : data[src].get(i);



		//Add other vertices into tentative set

		for (int i = 0; i < n; i++)

			if (i != src)



		//As long as tentative set is not empty, we iterate

		while (!t.isEmpty()){

			int s = t.size();	//Size of tentative node

			int min = 0;


			//If there is no edge between permanent set and tentative set, we exit

			for (int i = 1; i < s; i++){

				int m = t.elementAt(i);

				if (m!= src && val[t.elementAt(min)] > val[m])

					min = i;



			//Now we find the minimum path length

			int k = t.elementAt(min);		//Get the value of the node with minimum path length


			//The smallest value is destination, so we remove it

			if (k == dest)

				return val[dest];

			//If the minimum value is MAX, it means that there is no egdges left

			if (val[k] == MAX)

				return -1;


			//Remove from tentative set



			//Recalculate the value of the array val[]

			for (int i = 0; i < n; i++)

				if(i != src)


					int tmp = MAX;

					int u = data[k].get(i);

					//There is an edge between i and k, calculate the length

					if (u < MAX)					

						tmp = val[k] + u;

					//Update val[i] if we have smaller path length

					if (tmp < val[i])

						val[i] = tmp;




		//Return the value of the shortest path length from src to dest

		return val[dest];


Open in new window

Question by:paddy8788
    LVL 2

    Accepted Solution

    As I am not much into algorithms I went in looking for enough test cases that would help you validate the code.

    Here is a another version of Dijkstra source code with extensive test cases to validate the same.

    Would be glad to hear that helped you. Thanks for this question. :)
    LVL 16

    Expert Comment

    I don't get this
    for (int i = 0; i < n; i++)
                            if (i != src)

    why bothering to add all other nodes? even those unreachable.. shouldn't we add just the nodes reachable from the current cut?
    LVL 16

    Expert Comment

    Would you give me the code which you initialized the algorithm with?

    Expert Comment

    It is given a chess board with N*N squares. On the board there is a dice with the dimensions
    equal with one square on the board and occupies perfectly the surface of a square. On each side of
    the dice there is an integer value between 1 and 100.
    The dice can move by rotating itself with 90º around one of it`s edge on the board. With this
    move it can go in the upper, lower, left and right square. With more moves, the dice can go to each
    square on the board. The cost of a path is equal to the sum of the values on the side on the board,
    including the first and the last position.
    Giving you the dimension of the board N, the six values on the sides of the cube, the starting
    position and the final position, find a minimum path from the starting position to the finish one. You
    must save in a file the length of the minimum path and the path itself.
    Input data: file
    N // board dimension
    face back left right up down // the 6 values on the sides of the dice
    x1 y1 x2 y2 // the positions of the start and finish squares, with 1 to N numbering
    Output data: file cube.out
    C // the cost of the minimum path
    L // the length of the path, as number of moves of the dice
    x1 y1
    x2 y2
    xL yL // the positions of the squares in the path
    Observations: At the start, the cube is positioned with the face side in the positive direction of
    Oy axis, the right side on the positive direction of Ox and the top on the positive direction of
    All the coordinates start from 1.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Top 6 Sources for Identifying Threat Actor TTPs

    Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

    Suggested Solutions

    Title # Comments Views Activity
    Java MSI Solution 3 51
    Jasper Report: Crosstab Report- Include Page Footer 2 34
    mapBully challenge 6 51
    solarwind tftp server 2 16
    By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
    One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
    The viewer will learn how to implement Singleton Design Pattern in Java.
    This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

    758 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    13 Experts available now in Live!

    Get 1:1 Help Now