juice - 2 months ago 14

Java Question

`public int dijkstra(){`

boolean[] visited = new boolean[gSize];

int src = 1;

int dest = 1;

int[] distance = new int[5];

int[] part = new int[5];

int min;

int nextNode = 0;

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

{

visited[i] = false;

part[i] = 0;

for(int j = 0; j < 5; j++)

if(arr[i][j] == -1)

arr[i][j] = 999; //gives it a high value to ignore

}

distance = arr[src];

distance[src] = 0;

visited[src] = true;

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

{

min = 999;

for(int j = 0; j < 5; j++)

if(min > distance[j] && visited[j] != true)

{

min = distance[j];

nextNode = j;

}

visited[nextNode] = true;

for(int k = 0; k < 5; k++)

if(visited[k] != true)

if(min + arr[nextNode][k] < distance[k])

{

distance[k] = min + arr[nextNode][k];

part[k] = nextNode;

}

}

return distance[dest];

}

This Dijkstra algorithm works as it is supposed to. However, it works only from vertex 'x' to vertex 'y'. I can't, for the life of me, figure out how to find the shortest path from vertex 'x' to vertex 'x'.

For example:

From B to B the shortest path should return 9 (B -> C -> E -> B). Am I taking a wrong approach by thinking that Dijkstra's algorithm can solve this problem? Thank you!

Answer Source

You can search the shortest path starting from nodes adjacent to x and finishing to the node x.

The shortest path will be the shortest sum of path length from x to an adjacent node plus the shortest path length from this adjacent node to x.

Basically in pseudocode:

```
// Note: The function neighbors(x) returns the list of neighbors of node x
// The function distance(x, y) returns distance between node x and y
// applying dijkstra algorithm
shortestDistance = 0;
for (Node neighbor : neighbors(x)) {
currentDistance = distance(x, neighbor) + distance(neighbor, x);
shortestDistance = min(currentDistance, shortestDistance);
}
return shortestDistance;
```