I have the following graph (example) and I am developing a Shortest Path Algorithm.

The objective is to go from the entrance to the exit.

Randomly, a node will have his entering connections as a negative number.

Below is the code I have developed but sometimes it has a non desired behaviour.

For example if the random node is 42, the result Shortest Path is:

entrance->0->10->11->12->13->3->4->14->24->34->44-> exit

instead of

entrance->0->10->20->30->40->41->42->43->33->23->13->3->4->14->24->34->44->exit .

How can i fix it?

Here is my code:

```
public Iterator iteratorShortestPathConnectionCost(T startVertex, T targetVertex) {
int startIndex = this.getIndex(startVertex);
int targetIndex = this.getIndex(targetVertex);
int previousPosition = -1; //the variable will be used to store the previous vertice
double weight;
double[] pathWeight = new double[super.numVertices];//an array that will be used to store the weigth between the starter vertex and the other vertexes
double [] pathLength=new double[super.numVertices]; //an array that will be used to store the weigth between the starter vertex and the other vertexes
int[] previous = new int[super.numVertices]; //an array that stores the vertexs that belong to the shortest path
boolean[] visited = new boolean[super.numVertices]; //an array that tells if a vertex has already been visited or not
LinkedHeap<Double> traversalMinHeap = new LinkedHeap<>();
LinkedStack<Integer> invertedResult = new LinkedStack<>();
ArrayUnorderedList<T> resultList = new ArrayUnorderedList<>(10);
if (!indexIsValid(startIndex) || !indexIsValid(targetIndex)) {
return resultList.iterator();
}
//Set total weigth from starting vertex to all vertexs to infinity
for (int i = 0; i < super.numVertices; i++) {
pathWeight[i] = Double.POSITIVE_INFINITY;
}
//Set distance from starting vertex to all verteces to 0
for(int i=0;i<super.numVertices;i++){
pathLength[i]=Double.POSITIVE_INFINITY;
}
//Set weigth from starting vertex to himself to 0
pathWeight[startIndex] = 0;
pathLength[startIndex]=0;
//Set all vertexs as unvisited
for (int i = 0; i < super.numVertices; i++) {
visited[i] = false;
}
previous[startIndex] = -1;
//Visit the index with the smallest distance from starting vertex, that means visit the start index because the distance is 0
visited[startIndex] = true;
weight = 0;
for (int i = 0; i < super.numVertices; i++) {
if (!visited[i] && this.getAdjMatrixWeight()[startIndex][i] != Infinity) { //checks if the vertex has not been visited yet and if it is connected with start path
pathWeight[i] = pathWeight[startIndex] + this.getAdjMatrixWeight()[startIndex][i];
pathLength[i]=pathLength[startIndex]+1;
previous[i] = startIndex;
traversalMinHeap.addElement(pathWeight[i]);
}
}
do {
try {
weight = (traversalMinHeap.removeMin());
} catch (EmptyCollectionException ex) {
}
traversalMinHeap = new LinkedHeap<>();
// if (weight == Double.POSITIVE_INFINITY) {
// return resultList.iterator();
//} else {
//store previous
double distance=Double.POSITIVE_INFINITY;
for (int i = 0; i < super.numVertices; i++) {
if ((pathWeight[i] == weight) && !visited[i] && pathLength[i]<=distance ){
distance=pathLength[i];
for (int j = 0; j < super.numVertices; j++) {
if ((this.getAdjMatrixWeight()[i][j] != Infinity)) {
previousPosition = i;
}
}
}
}
if (previousPosition != -1) {
visited[previousPosition] = true;
} else { // if the previous position is -1 it´s because there were no vertexs connect to the starting vertex
return resultList.iterator();
}
//}
for (int i = 0; i < super.numVertices; i++) {
if (!visited[i]) {
if ((this.getAdjMatrixWeight()[previousPosition][i] != Infinity) && (pathWeight[previousPosition] + this.getAdjMatrixWeight()[previousPosition][i]) <pathWeight[i]) {
pathWeight[i] = pathWeight[previousPosition] + this.getAdjMatrixWeight()[previousPosition][i];
pathLength[i]=pathLength[previousPosition]+1;
previous[i] = previousPosition;
}
traversalMinHeap.addElement(pathWeight[i]);
}
}
} while (!traversalMinHeap.isEmpty() && !visited[targetIndex]);
previousPosition = targetIndex;
invertedResult.push(previousPosition);
do {
previousPosition = previous[previousPosition];
invertedResult.push(previousPosition);
} while (previousPosition != startIndex);
while (!invertedResult.isEmpty()) {
try {
resultList.addToRear(super.vertices[(invertedResult.pop())]);
} catch (EmptyCollectionException ex) {
}
}
return resultList.iterator();
}
```