# 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...

``````//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 tail;

public List(){
tail = null;
}

//Add edge with vertex x and length len
public void add(int x, int len){
Point p = new Point(x, len);

}
else{

tail.next = p;
tail = p;
}
}

//Get edge of vertex y
public int get(int y){
return MAX;
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){
return MAX;
{
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)

//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];
}
``````
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
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

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
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?
0
Commented:
Would you give me the code which you initialized the algorithm with?
0
Commented:
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
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.