Question

ALGORITHM DESIGN

Given a connected weighted graph, give a scheme to find the farthest node from a given source node. Note that you do not have to start from scratch, but use a known standard algorithm. Hint: Make sure use of a known algorithm for finding the shortest paths.

Answer 1

we can do it using dijkstra Algorithm

Following steps for implementing dijkstra using priority Queue.

1) At first,make an array equal to size of number of vertices in queue and initialize distances of all
vertices as INT_MIN.

2) Create an empty priority_queue p with every item as pair(weight, vertex).And each item are compared on basis
of their weight as priority.

3) now,put source vertex in p and initialize its weight as 0.

4) while p is not empty
a) Extract maximum distance vertex from p.
suppose it be u.
b) now,Loop through all adjacent of u and do
following for every vertex v.

If dist[v] < dist[u] + weight(u, v)

(i) Update distance of v
dist[v] = dist[u] + weight(u, v)
(ii) Insert v into the p (Even if v is
already there)

5) finally,print node having maximum value dist[] array.