QuestionQuestion

Task 1 - Implement Dijkstra algorithm to find the shortest path in a graph. Pseudocode for the algorithm is given below.

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 PreviewSolution 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;      
    }...
$93.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats