know both their vertex number and their distancewe create simple class for the purpose called dijkelemas follows dijkelem is quite similar to the edge class used by the adjacency list representation import java lang comparableclass dijkelem implements comparable private int vertexprivate int weightpublic dijkelem(int invint inwvertex invweight inwpublic dijkelem({vertex weight public int key(return weightpublic int vertex(return vertexpublic int compareto(dijkelem thatif (weight that key()return - else if (weight =that key()return else return figure shows an implementation for dijkstra' algorithm using the priority queue using minvertex to scan the vertex list for the minimum value is more efficient when the graph is densethat iswhen |eapproaches | | using priority queue is more efficient when the graph is sparse because its cost is th((| | |log | |howeverwhen the graph is densethis cost can become as great as th(| | log | |th(| | log | |figure illustrates dijkstra' algorithm the start vertex is all vertices except have an initial value of after processing vertex aits neighbors have their estimates updated to be the direct distance from after processing (the closest vertex to )vertices and are updated to reflect the shortest path through the remaining vertices are processed in order bdand minimum-cost spanning trees this section presents two algorithms for determining the minimum-cost spanning tree (mstfor graph the mst problem takes as input connectedundirected graph gwhere each edge has distance or weight measure attached the mst is the graph containing the vertices of along with the subset of ' edges that ( has minimum total cost as measured by summing the values for all of the edges