Modify all code below to handle vertices as String and run the programs.

/****************************************************************************** * Compilation: javac DijkstraSP.java * Execution: java DijkstraSP input.txt s * Dependencies: EdgeWeightedDigraph.java IndexMinPQ.java Stack.java DirectedEdge.java * Data files: https://algs4.cs.princeton.edu/44sp/tinyEWD.txt * https://algs4.cs.princeton.edu/44sp/mediumEWD.txt * https://algs4.cs.princeton.edu/44sp/largeEWD.txt * * Dijkstra's algorithm. Computes the shortest path tree. * Assumes all weights are nonnegative. * * % java DijkstraSP tinyEWD.txt 0 * 0 to 0 (0.00) * 0 to 1 (1.05) 0->4 0.38 4->5 0.35 5->1 0.32 * 0 to 2 (0.26) 0->2 0.26 * 0 to 3 (0.99) 0->2 0.26 2->7 0.34 7->3 0.39 * 0 to 4 (0.38) 0->4 0.38 * 0 to 5 (0.73) 0->4 0.38 4->5 0.35 * 0 to 6 (1.51) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 * 0 to 7 (0.60) 0->2 0.26 2->7 0.34 * * % java DijkstraSP mediumEWD.txt 0 * 0 to 0 (0.00) * 0 to 1 (0.71) 0->44 0.06 44->93 0.07 ... 107->1 0.07 * 0 to 2 (0.65) 0->44 0.06 44->231 0.10 ... 42->2 0.11 * 0 to 3 (0.46) 0->97 0.08 97->248 0.09 ... 45->3 0.12 * 0 to 4 (0.42) 0->44 0.06 44->93 0.07 ... 77->4 0.11 * ... * ******************************************************************************/ /** * The {@code DijkstraSP} class represents a data type for solving the * single-source shortest paths problem in edge-weighted digraphs * where the edge weights are nonnegative. * 
 * This implementation uses Dijkstra's algorithm with a binary heap. * The constructor takes time proportional to E log V, * where V is the number of vertices and E is the number of edges. * Each call to {@code distTo(int)} and {@code hasPathTo(int)} takes constant time; * each call to {@code pathTo(int)} takes time proportional to the number of * edges in the shortest path returned. * 
 * For additional documentation, * see Section 4.4 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class DijkstraSP { private double[] distTo; // distTo[v] = distance of shortest s->v path private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path private IndexMinPQ pq; // priority queue of vertices /** * Computes a shortest-paths tree from the source vertex {@code s} to every other * vertex in the edge-weighted digraph {@code G}. * * @param G the edge-weighted digraph * @param s the source vertex * @throws IllegalArgumentException if an edge weight is negative * @throws IllegalArgumentException unless {@code 0 <= s < V} */ public DijkstraSP(DirectedWeightedGraph G, int s) { distTo = new double[G.V()]; edgeTo = new DirectedEdge[G.V()]; validateVertex(s); for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY; distTo[s] = 0.0; // relax vertices in order of distance from s pq = new IndexMinPQ(G.V()); pq.insert(s, distTo[s]); while (!pq.isEmpty()) { int v = pq.delMin(); for (DirectedEdge e : G.getAdjW(v)) relax(e); } // check optimality conditions assert check(G, s); } // relax edge e and update pq if changed private void relax(DirectedEdge e) { int v = e.from(), w = e.to(); if (distTo[w] > distTo[v] + e.weight()) { distTo[w] = distTo[v] + e.weight(); edgeTo[w] = e; if (pq.contains(w)) pq.decreaseKey(w, distTo[w]); else pq.insert(w, distTo[w]); } } /** * Returns the length of a shortest path from the source vertex {@code s} to vertex {@code v}. * @param v the destination vertex * @return the length of a shortest path from the source vertex {@code s} to vertex {@code v}; * {@code Double.POSITIVE_INFINITY} if no such path * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public double distTo(int v) { validateVertex(v); return distTo[v]; } /** * Returns true if there is a path from the source vertex {@code s} to vertex {@code v}. * * @param v the destination vertex * @return {@code true} if there is a path from the source vertex * {@code s} to vertex {@code v}; {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public boolean hasPathTo(int v) { validateVertex(v); return distTo[v] < Double.POSITIVE_INFINITY; } /** * Returns a shortest path from the source vertex {@code s} to vertex {@code v}. * * @param v the destination vertex * @return a shortest path from the source vertex {@code s} to vertex {@code v} * as an iterable of edges, and {@code null} if no such path * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public Iterable pathTo(int v) { validateVertex(v); if (!hasPathTo(v)) return null; Stack path = new Stack(); for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) { path.push(e); } return path; } // check optimality conditions: // (i) for all edges e: distTo[e.to()] <= distTo[e.from()] + e.weight() // (ii) for all edge e on the SPT: distTo[e.to()] == distTo[e.from()] + e.weight() private boolean check(DirectedWeightedGraph G, int s) { // check that distTo[v] and edgeTo[v] are consistent if (distTo[s] != 0.0 || edgeTo[s] != null) { System.err.println("distTo[s] and edgeTo[s] inconsistent"); return false; } for (int v = 0; v < G.V(); v++) { if (v == s) continue; if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) { System.err.println("distTo[] and edgeTo[] inconsistent"); return false; } } // check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight() for (int v = 0; v < G.V(); v++) { for (DirectedEdge e : G.getAdjW(v)) { int w = e.to(); if (distTo[v] + e.weight() < distTo[w]) { System.err.println("edge " + e + " not relaxed"); return false; } } } // check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight() for (int w = 0; w < G.V(); w++) { if (edgeTo[w] == null) continue; DirectedEdge e = edgeTo[w]; int v = e.from(); if (w != e.to()) return false; if (distTo[v] + e.weight() != distTo[w]) { System.err.println("edge " + e + " on shortest path not tight"); return false; } } return true; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = distTo.length; if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } /** * Unit tests the {@code DijkstraSP} data type. * * @param args the command-line arguments */ public static void main(String[] args) { DirectedWeightedGraph wdg = new DirectedWeightedGraph(4); wdg.addEdge(new DirectedEdge(0, 1, 1.2)); wdg.addEdge(new DirectedEdge(1, 3, 1.4)); wdg.addEdge(new DirectedEdge(0, 2, 2.2)); wdg.addEdge(new DirectedEdge(2, 3, 2.4)); int s = 0; // compute shortest paths DijkstraSP sp = new DijkstraSP(wdg, s); // print shortest path for (int t = 0; t < wdg.V(); t++) { if (sp.hasPathTo(t)) { System.out.printf("%d to %d (%.2f) ", s, t, sp.distTo(t)); for (DirectedEdge e : sp.pathTo(t)) { System.out.print(e + " "); } System.out.println(); } else { System.out.printf("%d to %d no path ", s, t); } } } }

-------------------------------------------------------------------------------------------------------------------

/****************************************************************************** * Compilation: javac IndexMinPQ.java * Execution: java IndexMinPQ * Dependencies: StdOut.java * * Minimum-oriented indexed PQ implementation using a binary heap. * ******************************************************************************/ import java.util.Iterator; import java.util.NoSuchElementException; /** * The {@code IndexMinPQ} class represents an indexed priority queue of generic keys. * It supports the usual insert and delete-the-minimum * operations, along with delete and change-the-key * methods. In order to let the client refer to keys on the priority queue, * an integer between {@code 0} and {@code maxN - 1} * is associated with each keythe client uses this integer to specify * which key to delete or change. * It also supports methods for peeking at the minimum key, * testing if the priority queue is empty, and iterating through * the keys. * 
 * This implementation uses a binary heap along with an array to associate * keys with integers in the given range. * The insert, delete-the-minimum, delete, * change-key, decrease-key, and increase-key * operations take logarithmic time. * The is-empty, size, min-index, min-key, * and key-of operations take constant time. * Construction takes time proportional to the specified capacity. * 
 * For additional documentation, see Section 2.4 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne * * @param  the generic type of key on this priority queue */ public class IndexMinPQ> implements Iterable { private int maxN; // maximum number of elements on PQ private int n; // number of elements on PQ private int[] pq; // binary heap using 1-based indexing private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i private Key[] keys; // keys[i] = priority of i /** * Initializes an empty indexed priority queue with indices between {@code 0} * and {@code maxN - 1}. * @param maxN the keys on this priority queue are index from {@code 0} * {@code maxN - 1} * @throws IllegalArgumentException if {@code maxN < 0} */ public IndexMinPQ(int maxN) { if (maxN < 0) throw new IllegalArgumentException(); this.maxN = maxN; n = 0; keys = (Key[]) new Comparable[maxN + 1]; // make this of length maxN?? pq = new int[maxN + 1]; qp = new int[maxN + 1]; // make this of length maxN?? for (int i = 0; i <= maxN; i++) qp[i] = -1; } /** * Returns true if this priority queue is empty. * * @return {@code true} if this priority queue is empty; * {@code false} otherwise */ public boolean isEmpty() { return n == 0; } /** * Is {@code i} an index on this priority queue? * * @param i an index * @return {@code true} if {@code i} is an index on this priority queue; * {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= i < maxN} */ public boolean contains(int i) { if (i < 0 || i >= maxN) throw new IllegalArgumentException(); return qp[i] != -1; } /** * Returns the number of keys on this priority queue. * * @return the number of keys on this priority queue */ public int size() { return n; } /** * Associates key with index {@code i}. * * @param i an index * @param key the key to associate with index {@code i} * @throws IllegalArgumentException unless {@code 0 <= i < maxN} * @throws IllegalArgumentException if there already is an item associated * with index {@code i} */ public void insert(int i, Key key) { if (i < 0 || i >= maxN) throw new IllegalArgumentException(); if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue"); n++; qp[i] = n; pq[n] = i; keys[i] = key; swim(n); } /** * Returns an index associated with a minimum key. * * @return an index associated with a minimum key * @throws NoSuchElementException if this priority queue is empty */ public int minIndex() { if (n == 0) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } /** * Returns a minimum key. * * @return a minimum key * @throws NoSuchElementException if this priority queue is empty */ public Key minKey() { if (n == 0) throw new NoSuchElementException("Priority queue underflow"); return keys[pq[1]]; } /** * Removes a minimum key and returns its associated index. * @return an index associated with a minimum key * @throws NoSuchElementException if this priority queue is empty */ public int delMin() { if (n == 0) throw new NoSuchElementException("Priority queue underflow"); int min = pq[1]; exch(1, n--); sink(1); assert min == pq[n+1]; qp[min] = -1; // delete keys[min] = null; // to help with garbage collection pq[n+1] = -1; // not needed return min; } /** * Returns the key associated with index {@code i}. * * @param i the index of the key to return * @return the key associated with index {@code i} * @throws IllegalArgumentException unless {@code 0 <= i < maxN} * @throws NoSuchElementException no key is associated with index {@code i} */ public Key keyOf(int i) { if (i < 0 || i >= maxN) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); else return keys[i]; } /** * Change the key associated with index {@code i} to the specified value. * * @param i the index of the key to change * @param key change the key associated with index {@code i} to this key * @throws IllegalArgumentException unless {@code 0 <= i < maxN} * @throws NoSuchElementException no key is associated with index {@code i} */ public void changeKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); keys[i] = key; swim(qp[i]); sink(qp[i]); } /** * Change the key associated with index {@code i} to the specified value. * * @param i the index of the key to change * @param key change the key associated with index {@code i} to this key * @throws IllegalArgumentException unless {@code 0 <= i < maxN} * @deprecated Replaced by {@code changeKey(int, Key)}. */ @Deprecated public void change(int i, Key key) { changeKey(i, key); } /** * Decrease the key associated with index {@code i} to the specified value. * * @param i the index of the key to decrease * @param key decrease the key associated with index {@code i} to this key * @throws IllegalArgumentException unless {@code 0 <= i < maxN} * @throws IllegalArgumentException if {@code key >= keyOf(i)} * @throws NoSuchElementException no key is associated with index {@code i} */ public void decreaseKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); if (keys[i].compareTo(key) <= 0) throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key"); keys[i] = key; swim(qp[i]); } /** * Increase the key associated with index {@code i} to the specified value. * * @param i the index of the key to increase * @param key increase the key associated with index {@code i} to this key * @throws IllegalArgumentException unless {@code 0 <= i < maxN} * @throws IllegalArgumentException if {@code key <= keyOf(i)} * @throws NoSuchElementException no key is associated with index {@code i} */ public void increaseKey(int i, Key key) { if (i < 0 || i >= maxN) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); if (keys[i].compareTo(key) >= 0) throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key"); keys[i] = key; sink(qp[i]); } /** * Remove the key associated with index {@code i}. * * @param i the index of the key to remove * @throws IllegalArgumentException unless {@code 0 <= i < maxN} * @throws NoSuchElementException no key is associated with index {@code i} */ public void delete(int i) { if (i < 0 || i >= maxN) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); int index = qp[i]; exch(index, n--); swim(index); sink(index); keys[i] = null; qp[i] = -1; } /*************************************************************************** * General helper functions. ***************************************************************************/ private boolean greater(int i, int j) { return keys[pq[i]].compareTo(keys[pq[j]]) > 0; } private void exch(int i, int j) { int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; qp[pq[i]] = i; qp[pq[j]] = j; } /*************************************************************************** * Heap helper functions. ***************************************************************************/ private void swim(int k) { while (k > 1 && greater(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k <= n) { int j = 2*k; if (j < n && greater(j, j+1)) j++; if (!greater(k, j)) break; exch(k, j); k = j; } } /*************************************************************************** * Iterators. ***************************************************************************/ /** * Returns an iterator that iterates over the keys on the * priority queue in ascending order. * The iterator doesn't implement {@code remove()} since it's optional. * * @return an iterator that iterates over the keys in ascending order */ public Iterator iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator { // create a new pq private IndexMinPQ copy; // add all elements to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator() { copy = new IndexMinPQ(pq.length - 1); for (int i = 1; i <= n; i++) copy.insert(pq[i], keys[pq[i]]); } public boolean hasNext() { return !copy.isEmpty(); } public void remove() { throw new UnsupportedOperationException(); } public Integer next() { if (!hasNext()) throw new NoSuchElementException(); return copy.delMin(); } } /** * Unit tests the {@code IndexMinPQ} data type. * * @param args the command-line arguments */ public static void main(String[] args) { // insert a bunch of strings String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" }; IndexMinPQ pq = new IndexMinPQ(strings.length); for (int i = 0; i < strings.length; i++) { pq.insert(i, strings[i]); } // delete and print each key while (!pq.isEmpty()) { int i = pq.delMin(); System.out.println(i + " " + strings[i]); } System.out.println(); // reinsert the same strings for (int i = 0; i < strings.length; i++) { pq.insert(i, strings[i]); } // print each key using the iterator for (int i : pq) { System.out.println(i + " " + strings[i]); } while (!pq.isEmpty()) { pq.delMin(); } } }

----------------------------------------------------------------------------------------------------------------------------

public class DirectedEdge { private final int v; private final int w; private final double weight; public DirectedEdge(int v, int w, double weight) { this.v = v; this.w = w; this.weight = weight; } public int from() {return v;} public int to() { return w;} public double weight() { return weight;} public String toString() { return v + "->" + w + " " + String.format("%5.2f", weight); } }

----------------------------------------------------------------------------------------------------------------------------------------

import java.util.ArrayList; public class DirectedWeightedGraph extends Graph{ private ArrayList[] adjW; public DirectedWeightedGraph(int V) { super(V); adjW = (ArrayList[]) new ArrayList[V]; for (int v = 0; v < V; v++) { adjW[v] = new ArrayList(); } } public void addEdge(DirectedEdge e) { int v = e.from(); int w = e.to(); adjW[v].add(e); setE(E()+1); } public ArrayList getAdjW(int v) { return adjW[v]; } public String toString() { StringBuilder s = new StringBuilder(); s.append(V() + " " + E() + " "); for (int v = 0; v < V(); v++) { s.append(v + ": "); for (DirectedEdge e : adjW[v]) { s.append(e + " "); } s.append(" "); } return s.toString(); } }

---------------------------------------------------------------------------------------------------------------------

public class DirectedGraph extends Graph{ public DirectedGraph(int V) { super(V); } public void addEdge(int v, int u) { getAdj(v).add(u); setE(E()+1); } }