Friends Trip

In this approach, we will find the minimum distance between the source and every other node. Then we will reverse all the edges of the graph given and find the shortest distance between the destination and every other node. Then we will add the distances from both source and destination and add 1 to it. Then will be the maximum value of all the distances sum + 1.

We will create a function bellmanFord(edges, n, source). The parameter edge is the edge list, n is the number of nodes, and the source is the starting node. This function will return the list of distances of all nodes from the source.

Algorithm:

• The function bellmanFord(edges, n, source): where the parameter edges is the edge list, n is the number of nodes, and the source is the starting node.
  • Create a distances list of length n with all values initialized to the maximum value of the integer.
  • Set the distance of source distances[source] as 0
  • Iterate from 0 to n - 1
    • Iterate edge through the array edges
      • Set currSource as edge[0] - 1
      • Set currDest as edge[1] - 1.
      • Set weight as edge[2].
      • Set distances[currDest] as the minimum of distances[currDest] and the sum of distances[currSource] and weight.
  • After the while loop ends, return the list distances.
• Create an empty array revEdges
• Iterate edge through edges
  • Set source, destination, weight as edge[0], edge[1], edge[2], respectively
  • Insert the array [destination, source, weight] into revEdges
• Set startDistances as belmanFord(s - 1, edges, n)
• Set endDistances as belmanFord(d - 1, revEdges, n)
• Set ans as 0
• Iterate i from 0 to size of startDistances  - 1
  • If startDistances[i] or endDistances[i] equal to maximum value of integer
    • Return -1
  • Set ans as maximum of ans and startDistances[i] +  endDistances[i] + 1
• Finally, return ans

In this approach, we will do the same thing as the last approach, but we will use Dijkstra’s algorithm to find the distance between one node to every other node. Which is more efficient 

We will create a function dijkstra(source ,graph). The parameter graph is the adjacency list, and the source is the starting node. This function will return the list of distances of all nodes from the source.

Algorithm:

• The function  dijkstra(source ,graph):
  • Create a distances array of the size of graph length with all values initialized to the maximum value of the integer.
  • Set the distance of source distances[source] as 0
  • Initialise a priority queue pq. Each value is a list of 2 numbers in the queue first represents the distance(priority), and the second is the node.
  • Add start node to pq. Insert [0, source] in pq.
  • While pq size of greater than 0.
    • Get the top element curr from the front of pq. Get current node and current node’s distance from curr. Set currNode as curr[1] and currDistance as curr[0].
    • If the current node’s distance is larger than in the distances list, then move to the next node.
    • Otherwise, iterate through all the neighbours of the current node to get their distance.  Set the variable neighbourDistance as graph[currNode][neighbour] + currDistance.
    • We will check if distances[neightbour] are less than neighbourDistance.
      • Update distances[neighbour]  as neighbourDistance.
      • Create an array li containing a tuple of neighbourDistance and neighbour. Then add the list li to pq. 
  • After the while loop ends, return the list distances.
• Initialise 2 arrays of length n graph and revGraph
• Iterate edge through edges
  • Set u, v, w as edge[0], edge[1] and edge[2] respectively
  • Insert the array [v - 1, w] in graph[u-1]
  • Insert the array [u - 1, w] in revGraph[v-1]
• Set startDistance as dijkstra(s - 1, graph)
• Set endDistace as dijkstra(d - 1, revGraph)
• Set ans as 0
• Iterate i from 0 to size of startDistances  - 1
  • If startDistances[i] or endDistances[i] equal to maximum value of integer
    • Return -1
  • Set ans as maximum of ans and startDistances[i] +  endDistances[i] + 1
• Finally, return ans