• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 5489
  • Last Modified:

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

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!


//THE PART OF LINKED LIST:
 
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{
			
			tail.next = 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 = id.next;
		}
		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 = head.next;
			return val;
		}
		while (id.next != null)
		{
			if (id.next.p == x)
			{
				int val = id.next.len;
				id.next = id.next.next;
				return val;
			}
			id = id.next;
		}
		
		return MAX;
	}
	}
 
//THE PART OF DIJSKTRA SHORTEST PATH ALGORITHM
// 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)
				t.add(i);
	
		//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
			t.removeElementAt(min);
			
			//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

0
paddy8788
Asked:
paddy8788
  • 2
1 Solution
 
V4ForumsCommented:
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.

http://renaud.waldura.com/doc/java/dijkstra/renaud-waldura-dijkstra.zip

Would be glad to hear that helped you. Thanks for this question. :)
0
 
ai_ja_naiCommented:
I don't get this
for (int i = 0; i < n; i++)
                        if (i != src)
                                t.add(i)

why bothering to add all other nodes? even those unreachable.. shouldn't we add just the nodes reachable from the current cut?
0
 
ai_ja_naiCommented:
Would you give me the code which you initialized the algorithm with?
0
 
pinkky4realCommented:
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 cube.in
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
Oz.
All the coordinates start from 1.
Limits:
1<=N<=100
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now