juice juice - 2 months ago 14
Java Question

Algorithm to get shortest path from node to itself -- Adjacency Matrix -- Java

digraph

digraph

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;