i trying make existing implementation of prim's algorithm keep track distances source . since prim's , dijkstra's algorithm same. can't figure out missing something.
i know problem cannot figure out.
here code, how modify print shortest distance source other vertex. shortest distance stored in 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]; (int = 0; < no_of_vertices; i++) (int j = 0; j < no_of_vertices; j++) { result[i][j]= 0; if (graph[i][j] == 0) { graph[i][j] = integer.max_value; } } (int = 0; < 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; (int = 0; < no_of_vertices; i++) { if (visited[i] == true) { (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 :" + + " destination : " + j + " weight : " + min); } } } } counter++; } (int = 0; < no_of_vertices; i++) { system.out.println("source : 0" + " destination : " + + " distance : " + dist[i]); } (string str : arr) { system.out.println(str); } } } there mistake in calculation of distance array forgets add distance of intermediate nodes source destination.
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 intermediate edges don't added, because add current edge. want like:
if (dist[i] + graph[i][j] < dist[j]) dist[j] = dist[i] + graph[i][j]; and rid of min variable.
although algorithm not correct me. you're supposed pick node minimum d[] @ each step, , update node's neighbors wrote above, mark picked , never pick again.
