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!

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];
}
```

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?

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

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

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. :)