Sample output: s(0) b(5) c(6) a(8) d(infinity) e(infinity) f(infinity) This is w

Question

Sample output:

  s(0) b(5) c(6) a(8) d(infinity) e(infinity) f(infinity)

This is what I have so far.

class DistPar        // distance and parent
{                   // items stored in sPath array
   public int distance; //distance from start to this vertex
   public int parentVert; // current parent of this vertex
     
     
   public DistPar(int pv, int d) // constructor
   {
       distance = d;
       parentVert = pv;
   }
}

public class Vertex {

public char label; // label(e.g.'A')
public boolean isInTree;
//=====================================

public Vertex(char lab) // constructor
{
   label = lab;

isInTree = false;
}
} // end class vertex

public class Graph {

   private final int MAX_VERTS = 20;
   private final int INFINITY = 1000000;
   private Vertex vertexList[];       // list of vertices
   private int adjMat[] [];           // adjacency matrix
   private int nVerts;                   // current number of vertices
   private int nTree;                   // number of verts in tree
   private DistPar sPath[];           // array for shortest-path data
   private int currentVert;           // current vertex
   private int startToCurrent; // distance to currentVert

  
   //=============================================
  
   public Graph() // constructor
   {
       vertexList = new Vertex[MAX_VERTS];
       // adjacency matrix
       adjMat = new int [MAX_VERTS][MAX_VERTS];
       nVerts = 0;
       nTree = 0;
       for (int j = 0; j<MAX_VERTS; j++) // set adjacency
      
           for(int k=0; k<MAX_VERTS; k++)   // set adjacency
               adjMat[j][k] = INFINITY;
       sPath = new DistPar[MAX_VERTS]; // shortest paths
   } // end constructor
//=====================================================
   public void addVertex(char lab)
   {
       vertexList[nVerts++] = new Vertex(lab);
   }
   //==================================================
   public void addEdge(int start, int end, int weight)
   {
       adjMat[start][end] = weight; // (directed)
   }
//========================================================
   public void path()   //find all shortest paths
   {
       int startTree =0;               //start at vertex 0
       vertexList[startTree].isInTree = true;
       nTree = 1;                        // put it in tree
      
       // transfer row of distances from adjMat to sPath
       for(int j = 0; j<nVerts; j++)
       {
           int tempDist = adjMat[startTree] [j] ;
       sPath[j] = new DistPar(startTree, tempDist);
   }
   // until all vertices are in the tree
   while(nTree < nVerts)
   {
       int indexMin = getMin(); // get minimum from sPath
       int minDist = sPath[indexMin].distance;
       if(minDist == INFINITY) // if all infinite
       {
           System.out.println("There are unreachable vertices ");
           break;           // sPath is complete
       }
       else           // reset currentVert
       {
           currentVert = indexMin; // closest vert
           startToCurrent = sPath[indexMin].distance;
           // minimum distance from startTree is
           // to currentVert, and is startToCurrent
       }
       // put current vertex in tree
       vertexList[currentVert].isInTree = true;
       nTree++;
       adjust_sPath();           // update sPath[] array
   }// end while (nTree < nVerts
   displayPaths();               //display sPath[] contents
   nTree = 0;                   //clear tree
   for(int j=0; j<nVerts; j++)
       vertexList[j].isInTree = false;
} //end path
//===========================================================
public int getMin()   // get entry from sPath
{

   int minDist = INFINITY; // assume minimum
   int indexMin = 0;
   for(int j=1; j<nVerts; j++)       // for each vertex
   {                               // if it's in tree
       if(!vertexList[j].isInTree && sPath[j]. distance < minDist) // smaller than older one
       {
           minDist = sPath[j]. distance;
           indexMin = j;               // update minimum
       }
}   // end for // return index of minimum
   return indexMin;
}// end getMin()
//==========================================================
public void adjust_sPath()
{
   //adjust values in shortes.path array sPath
   int column = 1; /// skip starting vertex
   while (column < nVerts)       // go across columns
   {
       // if this colmn's vertex already in tree skip it
       if(vertexList[column].isInTree)
       {
           column++;          
           continue;
       }
       // calculate distance for one sPath entry
       // get edge from currentVert to column
       int currentToFringe = adjMat[currentVert][column];
       // add distance from start
       int startToFringe = startToCurrent + currentToFringe;
       // get distance of current sPath entry
       int sPathDist = sPath[column].distance;
       // compare distance from start with sPath entry
       if(startToFringe < sPathDist) // if shorteer
       {
           sPath[column].parentVert = currentVert;
           sPath[column].distance = startToFringe;
          
       }
       column++;
   } // end while(column < nVerts
} // end adjust_sPath
//==============================================================
public void displayPaths()
{
   for (int j = 0; j<nVerts; j++) // display contents of sPath[]
   {
       System.out.print(vertexList[j].label + "="); //B=
       if (sPath[j].distance == INFINITY)
           System.out.print("inf");               // inf
       else
           System.out.print(sPath[j].distance);   // 50
           char parent = vertexList[sPath[j].parentVert].label;
           System.out.print("(" + parent + ")");   // (A)
   }
   System.out.println("");
}
//=====================================================
} // end class Graph

class PathApp {

public static void main(String[]args)
{
   Graph theGraph = new Graph();
   theGraph.addVertex('A'); // 0 (start)
   theGraph.addVertex('C'); // 2 (start)
   theGraph.addVertex('B'); // 1 (start)
   theGraph.addVertex('D'); // 3 (start)
   theGraph.addVertex('E'); // 4 (start)
  
  
   theGraph.addEdge(0,1,50); // AB 50
   theGraph.addEdge(0,3,80); // AD 80
   theGraph.addEdge(1,2,60); // BC 60
   theGraph.addEdge(1,3,90); // BD 90
   theGraph.addEdge(2,4,40); // CE 40
   theGraph.addEdge(0,0,5); // DC 20
   theGraph.addEdge(3,4,70); // DE 70
   theGraph.addEdge(4,1,50); // EB 50
   System.out.println("Shortest paths");
   theGraph.path();       // shortest paths
   System.out.println();
} // end main()
} // end class PathAPP

Explanation / Answer

import java.io.*;
import java.util.*;

public class Dijkstra {
private static final Graph.Edge[] GRAPH = {
new Graph.Edge("a", "b", 7),
new Graph.Edge("a", "c", 9),
new Graph.Edge("a", "f", 14),
new Graph.Edge("b", "c", 10),
new Graph.Edge("b", "d", 15),
new Graph.Edge("c", "d", 11),
new Graph.Edge("c", "f", 2),
new Graph.Edge("d", "e", 6),
new Graph.Edge("e", "f", 9),
};
private static final String START = "a";
private static final String END = "e";

public static void main(String[] args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
//g.printAllPaths();
}
}

class Graph {
private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges

/** One edge of the graph (only used by Graph constructor) */
public static class Edge {
public final String v1, v2;
public final int dist;
public Edge(String v1, String v2, int dist) {
this.v1 = v1;
this.v2 = v2;
this.dist = dist;
}
}

/** One vertex of the graph, complete with mappings to neighbouring vertices */
public static class Vertex implements Comparable<Vertex> {
public final String name;
public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
public Vertex previous = null;
public final Map<Vertex, Integer> neighbours = new HashMap<>();

public Vertex(String name) {
this.name = name;
}

private void printPath() {
if (this == this.previous) {
System.out.printf("%s", this.name);
} else if (this.previous == null) {
System.out.printf("%s(unreached)", this.name);
} else {
this.previous.printPath();
System.out.printf(" -> %s(%d)", this.name, this.dist);
}
}

public int compareTo(Vertex other) {
return Integer.compare(dist, other.dist);
}
}

/** Builds a graph from a set of edges */
public Graph(Edge[] edges) {
graph = new HashMap<>(edges.length);

//one pass to find all vertices
for (Edge e : edges) {
if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
}

//another pass to set neighbouring vertices
for (Edge e : edges) {
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
//graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
}
}

/** Runs dijkstra using a specified source vertex */
public void dijkstra(String startName) {
if (!graph.containsKey(startName)) {
System.err.printf("Graph doesn't contain start vertex "%s" ", startName);
return;
}
final Vertex source = graph.get(startName);
NavigableSet<Vertex> q = new TreeSet<>();

// set-up vertices
for (Vertex v : graph.values()) {
v.previous = v == source ? source : null;
v.dist = v == source ? 0 : Integer.MAX_VALUE;
q.add(v);
}

dijkstra(q);
}

/** Implementation of dijkstra's algorithm using a binary heap. */
private void dijkstra(final NavigableSet<Vertex> q) {
Vertex u, v;
while (!q.isEmpty()) {

u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable

//look at distances to each neighbour
for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
v = a.getKey(); //the neighbour in this iteration

final int alternateDist = u.dist + a.getValue();
if (alternateDist < v.dist) { // shorter path to neighbour found
q.remove(v);
v.dist = alternateDist;
v.previous = u;
q.add(v);
}
}
}
}

/** Prints a path from the source to the specified vertex */
public void printPath(String endName) {
if (!graph.containsKey(endName)) {
System.err.printf("Graph doesn't contain end vertex "%s" ", endName);
return;
}

graph.get(endName).printPath();
System.out.println();
}
/** Prints the path from the source to every vertex (output order is not guaranteed) */
public void printAllPaths() {
for (Vertex v : graph.values()) {
v.printPath();
System.out.println();
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.