Can someone please implement this method

Please show me the implementation of this code with a Graph class (provided) please do not use a matrix thank you

private static void dijkstra(Graph g, double[] dist, int[] pred, int source, int destination)

with the following pseudocode:

Here is the Graph file

import java.util.ArrayList; import java.util.function.Function;

public class Graph> implements GraphAPI { /* * number of vertices (size of this graph) */ private long order; /** * pointer to the list of vertices */ private Vertex first; /** * A vertex of a graph stores a data item and references * to its edge list and the succeeding vertex. The data * object extends the comparable interface. */ private class Vertex { /** * pointer to the next vertex */ public Vertex pNextVertex; /** * the data item */ public E data; /** * indegree */ public long inDeg; /** * outdegree */ public long outDeg; /** * pointer to the edge list */ public Edge pEdge; /** * Field for tracking vertex accesses */ public long processed; } /** * An edge of a graph contains a reference to the destination * vertex, a reference to the succeeding edge in the edge list and * the weight of the directed edge. */ private class Edge { /** * pointer to the destination vertex */ public Vertex destination; /** * weight on this edge */ public Double weight; /** * pointer to the next edge */ public Edge pNextEdge; } /** * Constructs an empty weighted directed graph */ public Graph() { first = null; order = 0; }

@Override public void insertVertex(E obj) { Vertex newPtr; Vertex locPtr; Vertex predPtr;

newPtr = new Vertex(); newPtr.pNextVertex = null; newPtr.data = obj; newPtr.inDeg = 0; newPtr.outDeg = 0; newPtr.processed = 0; newPtr.pEdge = null;

locPtr = first; predPtr = null; while (locPtr != null && obj.compareTo(locPtr.data) > 0) { predPtr = locPtr; locPtr = locPtr.pNextVertex; } /*key already exist. */ if (locPtr != null && obj.compareTo(locPtr.data)==0) { locPtr.data = obj; return; } /* insert before first vertex */ if (predPtr == null) first = newPtr; else predPtr.pNextVertex = newPtr; newPtr.pNextVertex = locPtr; order++; }

@Override public void deleteVertex(E key) { Vertex predPtr; Vertex walkPtr; if (isEmpty()) return; predPtr = null; walkPtr = first; while (walkPtr != null && key.compareTo(walkPtr.data) > 0) { predPtr = walkPtr; walkPtr = walkPtr.pNextVertex; } if (walkPtr == null || key.compareTo(walkPtr.data) != 0) return; /* vertex found. Test degree */ if ((walkPtr.inDeg > 0) || (walkPtr.outDeg > 0)) return; /* OK to delete */ if (predPtr == null) first = walkPtr.pNextVertex; else predPtr.pNextVertex = walkPtr.pNextVertex; order--; }

@Override public void insertEdge(E fromKey, E toKey, Double weight) { Edge tmpEdge; Edge newEdge; Edge pred; Vertex tmpFrom; Vertex tmpTo; if (isEmpty()) return; newEdge = new Edge(); /* check whether originating vertex exists */ tmpFrom = first; while (tmpFrom != null && fromKey.compareTo(tmpFrom.data) > 0) tmpFrom = tmpFrom.pNextVertex; if (tmpFrom == null || fromKey.compareTo(tmpFrom.data) != 0) return; /* locate destination vertex */ tmpTo = first; while (tmpTo != null && toKey.compareTo(tmpTo.data) > 0) tmpTo = tmpTo.pNextVertex; if (tmpTo == null || toKey.compareTo(tmpTo.data) != 0) return; /*check if edge already exists */ tmpEdge = tmpFrom.pEdge; while (tmpEdge != null && tmpEdge.destination != tmpTo) tmpEdge = tmpEdge.pNextEdge; if (tmpEdge != null && tmpEdge.destination != null) return; tmpFrom.outDeg++; tmpTo.inDeg++; newEdge.destination = tmpTo; newEdge.weight = weight; newEdge.pNextEdge = null; if (tmpFrom.pEdge == null) { tmpFrom.pEdge = newEdge; return; } pred = null; tmpEdge = tmpFrom.pEdge; while (tmpEdge != null && tmpEdge.destination != tmpTo) { pred = tmpEdge; tmpEdge = tmpEdge.pNextEdge; } if (pred == null) tmpFrom.pEdge = newEdge; else pred.pNextEdge = newEdge; newEdge.pNextEdge = tmpEdge; }

@Override public void deleteEdge(E fromKey, E toKey) { Edge tmpEdge; Edge newEdge; Edge pred; Vertex tmpFrom; Vertex tmpTo; newEdge = new Edge(); /* find source vertex */ tmpFrom = first; while (tmpFrom != null && fromKey.compareTo(tmpFrom.data)>0) tmpFrom = tmpFrom.pNextVertex; if (tmpFrom == null || fromKey.compareTo(tmpFrom.data) != 0) return; /* locate destination vertex */ tmpTo = first; while (tmpTo != null && toKey.compareTo(tmpTo.data)>0) tmpTo = tmpTo.pNextVertex; if (tmpTo == null || toKey.compareTo(tmpTo.data) != 0) return; /*check if edge does not exist */ tmpEdge = tmpFrom.pEdge; pred = null; while (tmpEdge != null && tmpEdge.destination != tmpTo) { pred = tmpEdge; tmpEdge = tmpEdge.pNextEdge; } /* if edge does not exist */ if (tmpEdge == null) return; /* update degrees */ if (pred != null) pred.pNextEdge = tmpEdge.pNextEdge; tmpFrom.outDeg--; tmpTo.inDeg--; }

@Override public Double retrieveEdge(E fromKey, E toKey) throws GraphException { Edge tmpEdge; Edge newEdge; Edge pred; Vertex tmpFrom; Vertex tmpTo; newEdge = new Edge(); /* find source vertex */ tmpFrom = first; while (tmpFrom != null && fromKey.compareTo(tmpFrom.data)>0) tmpFrom = tmpFrom.pNextVertex; if (tmpFrom == null || fromKey.compareTo(tmpFrom.data) != 0) throw new GraphException("Non-existent edge - retrieveEdge()."); /* locate destination vertex */ tmpTo = first; while (tmpTo != null && toKey.compareTo(tmpTo.data)>0) tmpTo = tmpTo.pNextVertex; if (tmpTo == null || toKey.compareTo(tmpTo.data) != 0) throw new GraphException("Non-existent edge - retrieveEdge()."); /*check if edge does not exist */ tmpEdge = tmpFrom.pEdge; pred = null; while (tmpEdge != null && tmpEdge.destination != tmpTo) { pred = tmpEdge; tmpEdge = tmpEdge.pNextEdge; } /* if edge does not exist */ if (tmpEdge == null) throw new GraphException("Non-existent edge - retrieveEdge()."); return tmpEdge.weight; }

@Override public E retrieveVertex(E key) throws GraphException { Vertex tmp; if (isEmpty()) throw new GraphException("Non-existent vertex - retrieveVertex()."); tmp = first; while (tmp != null && key.compareTo(tmp.data) != 0) tmp = tmp.pNextVertex; if (tmp == null) throw new GraphException("Non-existent vertex - retrieveVertex()."); return tmp.data; }

@Override public void bfsTraverse(Function func) { if (isEmpty()) return; Vertex walkPtr = first; while (walkPtr != null) { walkPtr.processed = 0; walkPtr = walkPtr.pNextVertex; } ArrayList queue = new ArrayList(); Vertex toPtr; Edge edgeWalk; Vertex tmp; walkPtr = first; while (walkPtr != null) { if (walkPtr.processed stack = new ArrayList(); Vertex toPtr; Edge edgeWalk; Vertex tmp; walkPtr = first; while (walkPtr != null) { if (walkPtr.processed

@Override public boolean isEmpty() { return first == null; }

@Override public long size() { return order; }

@Override public boolean isVertex(E key) { Vertex tmp; if (isEmpty()) return false; tmp = first; while (tmp != null && key.compareTo(tmp.data) != 0) tmp = tmp.pNextVertex; return tmp != null; } @Override public boolean isEdge(E fromKey, E toKey)//works { Vertex v = first; while(v != null) { if(v.data.equals(fromKey)) { Edge e = v.pEdge; while(e != null) { if(e.destination.data.equals(toKey)) return true; e = e.pNextEdge; } return false; } else { v = v.pNextVertex; } } return false; }

@Override public boolean isPath(E fromKey, E toKey) { if (isEmpty()) return false; Vertex vertex = first; while(vertex != null && vertex.data.compareTo(fromKey) != 0) { vertex = vertex.pNextVertex; } if(vertex == null) return false; ArrayList toDo = new ArrayList(); ArrayList visited = new ArrayList(); toDo.add(vertex); while (!toDo.isEmpty()) { vertex = toDo.remove(0); if(vertex.data.compareTo(toKey) == 0) return true; visited.add(vertex); Edge e = vertex.pEdge; while(e != null) { if(!visited.contains(e.destination)) toDo.add(e.destination); e = e.pNextEdge; } } return false; }

@Override public long countEdges() { long edgeTotal = 0; Vertex tmpV = first; while (tmpV != null) { edgeTotal = edgeTotal + tmpV.outDeg; tmpV = tmpV.pNextVertex; } return edgeTotal; }

@Override public long outDegree(E key) throws GraphException { Vertex tmp; if (isEmpty()) throw new GraphException("Non-existent vertex - outDegree()."); tmp = first; while (tmp != null && key.compareTo(tmp.data) != 0) tmp = tmp.pNextVertex; if (tmp == null) throw new GraphException("Non-existent vertex - outDegree()."); return tmp.outDeg; }

@Override public long inDegree(E key) throws GraphException { Vertex tmp; if (isEmpty()) throw new GraphException("Non-existent vertex - inDegree()."); tmp = first; while (tmp != null && key.compareTo(tmp.data) != 0) tmp = tmp.pNextVertex; if (tmp == null) throw new GraphException("Non-existent vertex - inDegree()."); return tmp.inDeg; } }

Here is a test graph as well:(you can use just a .txt for it)

p 5 6

c This graph consists of 5 vertices and 25 edges

c cities.gph

c vertices

n 1 A

n 2 B

n 3 C

n 4 D

n 5 E

cThese are the weighted edges

e 1 2 3

e 1 3 2

e 2 4 5

e 2 5 3

e 3 4 2

e 4 5 1

here is also a City class:

public class City implements Comparable { /** * name of label of the city */ private String label; /** * unique code for this city */ private Integer key; /** * Creates a city with the specified code and label * @param aKey unique code for the city * @param aLabel label for this city */ public City(Integer aKey, String aLabel) { label = aLabel; key = aKey; }

/** * Creates an anonymous city with the specified code * @param aKey code for the city */ public City(Integer aKey) { label = " "; key = aKey; }

/** * Gives the label associated with this city * @return the label of this city */ public String getLabel() { return label; } /** * Gives the unique code for this city * @return the code for this city */ public Integer getKey() { return key; }

/** * Compares the code for two cities * @param another a reference to a city * @return -1 when the key for this city comes after the * specified city, 0 when the keys are identical, otherwise, 1. */ public int compareTo(City another) { return key.compareTo(another.key); } }

Here's a method to read the file as well:(can go in main file)

private static Graph readGraph(String filename) { try { Graph newGraph = new Graph(); try (FileReader reader = new FileReader(filename)) { char temp; City c1, c2, aCity; String tmp; int k, m, v1, v2, j, size=0, nEdges=0; Integer key, v1Key,v2Key; Double weight; Scanner in = new Scanner(reader); while (in.hasNext()) { tmp = in.next(); temp = tmp.charAt(0); if (temp == 'p') { size = in.nextInt(); nEdges = in.nextInt(); } else if (temp == 'c') { in.nextLine(); } else if (temp == 'n') { key = in.nextInt(); tmp = in.nextLine(); aCity = new City(key,tmp); newGraph.insertVertex(aCity); } else if (temp == 'e') { v1Key = in.nextInt(); v2Key = in.nextInt(); weight = in.nextDouble(); c1 = new City(v1Key); c2 = new City(v2Key); newGraph.insertEdge(c1,c2,weight); } } } return newGraph; } catch(IOException exception) { System.out.println("Error processing file: "+exception); } return null; }

Thank you in advance.

Dijkstra Algorithm ALGORITHM: Dijkstra(G,s,d) Input: G a weighted graph with n vertices sa vertex of G, the source d - a vertex of G, the destination Output: dist - the shortest distance from s to other vertices predO - the predecessor of the apecified vertex) numSeen