# Dijkstra's print algorithm

I am trying to make my existing implementation of Prim's algorithm to keep track of distances from a source. As prim and Dijkstra algorithms are almost the same. I cannot figure out where I am missing something.

I know what the problem is, but I can't figure it out.

Here is my code on how to modify it to print the shortest distance from the source to all other vertices. The minimum distance is stored in an array named: dist []

code:

``````package Graphs;

import java.util.ArrayList;

public class Prims {

static int no_of_vertices = 0;

public static void main(String[] args) {
int[][] graph = {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
};
no_of_vertices = graph.length;
int [][] result =  new int [no_of_vertices][no_of_vertices];
boolean[] visited = new boolean[no_of_vertices];
int dist[] = new int[no_of_vertices];
for (int i = 0; i < no_of_vertices; i++)
for (int j = 0; j < no_of_vertices; j++) {
result[i][j]= 0;
if (graph[i][j] == 0) {
graph[i][j] = Integer.MAX_VALUE;
}
}

for (int i = 0; i < no_of_vertices; i++) {
visited[i] = false;
dist[i] = 0;

}
ArrayList<String> arr = new ArrayList<String>();
int min;
visited[0] = true;
int counter = 0;
while (counter < no_of_vertices - 1) {
min = 999;
for (int i = 0; i < no_of_vertices; i++) {
if (visited[i] == true) {
for (int j = 0; j < no_of_vertices; j++) {
if (!visited[j] && min > graph[i][j]) {
min = graph[i][j];
dist[i] += min; //  <------ Problem here
visited[j] = true;
arr.add("Src :" + i + " Destination : " + j
+ " Weight : " + min);
}
}
}
}
counter++;
}

for (int i = 0; i < no_of_vertices; i++) {
System.out.println("Source :  0" + " Destination : " + i
+ " distance : " + dist[i]);
}

for (String str : arr) {
System.out.println(str);
}
}
}
```

```

An error occurs when calculating the distance array because it forgets to add the distance between any intermediate nodes from the source to the destination.

+3

source to share

``````for (int j = 0; j < no_of_vertices; j++) {
if (!visited[j] && min > graph[i][j]) {
min = graph[i][j];
dist[i] += min; //  <------ Problem here
```

```

Of course no intermediate edges are added because you are only adding the current edge. You probably want something like:

``````if (dist[i] + graph[i][j] < dist[j])
dist[j] = dist[i] + graph[i][j];
```

```

And get rid of the variable `min`

.

Though your algorithm doesn't look correct to me. You have to select the node with the minimum `d[]`

at each step and update that node is neighbors as I wrote above, then mark it as selected and never select it again.

+2

source

All Articles