Dijkstra - need multiple paths
in
Programming Questions
•
2 years ago
I need some help with getting multiple paths (top 3) from Dijkstra's algorithm. Below is the code that produces the first path, but I can't figure out how to get the next two (if they exist). I believe the solution may be in modifying printPath, because creation of the class seems to create a list of all paths from the start node. Any help would be much appreciated.
- public class Dijkstra {
- // Dijkstra's algorithm to find shortest path from s to all other nodes
- public int [] dijkstra (Graph G, int start) {
- final int [] distance = new int [G.getNodeCount()]; // shortest known distance from "s"
- final int [] preceeding = new int [G.getNodeCount()]; // preceeding node in path
- final boolean [] visited = new boolean [G.getNodeCount()]; // all false initially
- for (int i=0; i<distance.length; i++) {
- distance[i] = Integer.MAX_VALUE;
- }
- distance[start] = 0;
- for (int i=0; i < distance.length; i++) {
- final int next = minVertex (distance, visited);
- visited[next] = true;
- // The shortest path to next is distance[next] and via preceeding[next].
- final Object[] n = G.neighbors (next);
- for (int j=0; j<n.length; j++) {
- final Node n1 = (Node) n[j];
- final int v = n1.id;
- final int d = distance[next] + 1; // + G.getWeight(next,v);
- if (distance[v] > d) {
- distance[v] = d;
- preceeding[v] = next;
- }
- }
- }
- return preceeding; // (ignore preceeding[start]==0!)
- }
- private int minVertex (int [] distance, boolean [] v) {
- int x = Integer.MAX_VALUE;
- int y = -1; // graph not connected, or no unvisited vertices
- for (int i=0; i<distance.length; i++) {
- if (!v[i] && distance[i]<x) {y=i; x=distance[i];}
- }
- return y;
- }
- public void printPath (Graph G, int [] preceeding, int start, int end) {
- ArrayList[] path = new ArrayList[3];
path[0] = new ArrayList();
path[1] = new ArrayList();
path[2] = new ArrayList(); - int x = end;
- while (x!=start) {
- path[0].add (0, G.getLabel(x));
- x = preceeding[x];
- }
- path[0].add (0, G.getLabel(start));
- }
- }
1
