Question
DIJKSTRA(G, w, s)
INIT-SINGLE-SOURCE(G, s)
S = Ø //empty
Q = G.V // i.e., insert all vertices Q
while Q != Ø
u = EXTRACT-MIN(Q)
S = S U {u}
for each vertex v ∈ G.Adj[u]
RELAX(u, v, w)
INITIALIZE-SINGLE-SOURCE(G, s)
 for each vertex v ∈ G.V
v.d = ∞
v.π = NIL
s.d = 0
RELAX(u, v, w)
if(v.d > u.d + w(u, v)
v.d = u.d + w(u, v)
v.π = u
Init-Single-Source and Relax is using algorithms A Finding the shortest path in a graph. Extract-Min extract the smallest element from a priority queue.
Task 2 - Find Shortest Route
In this task you use the Dijkstra algorithm to find the shortest path.
Task 2 - A
You will build a graph of the road network in England. You get to decide the level of detail themselves, but the graph should have a minimum of 20 places. Objects associated with a direct connection to have an edge between them, which indicate the distance between objects. The graph should be included in the report.
Use Dijkstra algorithm to find the shortest path between different locations in England and reports the route details.
Task 2 - B
You should create one (or more) graph(s) representing the game board. Each node is a position on the board and there are edges between neighboring nodes, which indicate how much life that will be lost to cross between two nodes. The point is to find the distance between two positions on the board that provides the most points ie the way that does the most damage.
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
public class graph {Vector<vertex> vertexs;
final int max_int = 9999999;
public graph() {
vertexs = new Vector<>();
}
/*
@param :String name
create a new vertex add to vertexs
return vertex that was create
*/
public vertex addNode(String name){
vertex n = new vertex(name);
vertexs.add(n);
return vertexs.get(vertexs.size() - 1);
}
/*
@param : tring sname
return vertex invertexs that has name
return null if no vertex found
*/
public vertex getNode(String sname){
for (vertex object : vertexs) {
if (object.name.equals(sname)) {
return object;
}
}
return null;
}...