Answer to Question #289871 in C++ for Mark

Question

Implement the following algorithm for the single source shortest path problem in a directed weighted graph. You must use a min-priority queue to implement Q in the pseudocode. For priority queue, you are allowed to use the priority queue provided by the STL library or your own implementation. You must take input from the user.

function dijkstra(G)
    for each v ∈ V
        d[V] = infinite
      d[s] = 0;S = ∅;Q =V;
     
    while Q IS NOT EMPTY
        U = ExtractMIN (Q);
        S = S ∪ {u};
        for each V ∈ u->ADJ[]
          if (d[v] > d[u]+w(u,v))
              d[v] = d[u]+w(u,v);
               p[v] = u;
    

Sample Input:

V E

u v weight(u,v)

… Src node

4 5

0 1 10

0 2 6

0 3 5

1 3 15

2 3 4

1

Sample Output

no path from 1 to 0

sp from 1 to 1: 1, length: 0

no path from 1 to 2

sp from 1 to 3: 1-->3, length: 15

Answer 1

Dear Mark, your question requires a lot of work, which neither of our experts is ready to perform for free. We advise you to convert it to a fully qualified order and we will try to help you. Please click the link below to proceed: Submit order