Single Source Shortest Path

Approach: 

• The brute force algorithm for finding the shortest path in an undirected graph with unit distances exhaustively checks all possible paths between two given vertices and selects the shortest one.
• Here is the step-by-step algorithm for each node:
  • Initialize a variable ‘minimumLength’ to store the shortest path found.
  • For each pair of vertices (‘start_vertex’, ‘end_vertex’) in the graph, do the following:
    • Initialize an empty list ‘currentLength’ to store the current path being explored.
    • Use a depth-first search (DFS) algorithm to find all possible paths between ‘start_vertex’ and ‘end_vertex’. During the DFS, maintain a visited array to avoid cycles.
    • For each path found during the DFS, compare its length to the value of ‘minimumLength’. If the ‘currentLength’ is shorter, update ‘minimumLength’ to the ‘currentLength’.
  • Once all pairs of vertices have been processed, ‘minimumLength’ will contain the shortest path in the graph.
  • Insert the value of ‘minimumLength’ in the ‘answer’ array.
• Return the ‘answer’ array.

 

Algorithm:

Function void DFS(int node, int dest, int[][] adjacencyList, int &minimumLength, int currentLength):

1. If ‘node’ equals ‘dest’:
   1. Update ‘minimumLength’ with a minimum of ‘minimumLength’ and ‘currentLength’.
   2. Return
2. Mark ‘visited[node]’ as true.
3. For each ‘i’ in ‘adjacencyList[node]’:
   1. If ‘visited[i]’ is not visited:
      1. DFS(‘i’, ‘dest’, ‘adjacencyList’, ‘minimumLength’, ‘currentLength’+1)
4. Mark ‘visited[node]’ as false.

Function int[] shortestPath(int n, int[] edges, int src):

1. Initialize an ‘answer’ array of length ‘N’ with 0.
2. Iterate over the edges and create the ‘adjacencyList’ for the graph.
3. For ‘node’ from 0 to ‘N’-1:
   1. Initialize an integer variable ‘minimumLength’ with a verge large integer value and ‘currentLength’ with 0.
   2. Initialize an empty boolean array ‘visited’ with false.
   3. Call DFS(‘node’, ‘src’, ‘adjacencyList’ ‘minimumLength’, ‘currentLength’, 0)
   4. ‘answer[i]’=’minimumLength’
4. Return ‘answer’

Approach: 

• Declare a min-heap array, 'minHeap', to hold the shortest distance between the source and destination vertices. The 'minHeap' has a size of N (number of vertexes).
• Set the 'src' index to 0 and the remaining indices to infinity. We act this way since we want our source vertex to be 'src.
• Create a priority queue to hold all of the visited vertices now.
• Repeat while there are still items in our priority queue.
  • Find the shortest route from the source vertex to each vertex in our input graph by going through each node.
  • Update the 'minHeap' value with the current lower value if the traversal cost of the current path is lower than the traversal cost recorded in the 'minHeap'.
  • Add the vertex's updated route cost to the priority queue.
• Send back the 'minHeap' array containing the lowest route costs between each source and vertex.

Algorithm:

Function int[] shortestPath(int N, int[] edges, int src):

1. Iterate over the edges and create the 'adjacencyList' for the graph.
2. Initialize an array 'minHeap' of size 'N' (number of vertices) and set all values to infinity except 'minHeap[src]' = 0.
3. Create a priority queue 'pq' to store visited vertices.
4. Enqueue a pair(vertices, cost) with vertex as source and cost as 0 into 'pq'.
5. While 'pq' is not empty, do the following:
   1. Dequeue a pair 'current' from 'pq'.
   2. Let 'u' be 'current.first' and 'cost' be 'current.second'.
   3. If 'cost' > 'minHeap[u]', continue to the next iteration.
   4. For each neighbor vertex 'v' of 'u' in 'adjacencyList[u]':
      1. Calculate 'newCost' = 'cost' + 1.
      2. If 'newCost' < 'minHeap[v]', update 'minHeap[v]' with 'newCost'.
      3. Enqueue a Node with vertex as 'v' and cost as 'newCost' into 'pq'.
6. For each value of 'minHeap' array, update infinity with -1.
7. Return the minHeap array representing the minimum path costs from the source to each vertex.

Approach: 

• Create a queue to store the vertices to be visited.
• Create an array to keep track of visited vertices.
• Create an array to store the distances from the source vertex to all other vertices.
• Initialize the distance array with infinity for all vertices except the source vertex ‘src’, which is initialized with 0.
• Enqueue the source vertex ‘src’ into the queue.
• While the queue is not empty, do the following:
  • Dequeue a vertex from the queue.
  • For each adjacent vertex of the dequeued vertex that has not been visited, do the following:
    • Mark the adjacent vertex as visited.
    • Update the distance of the adjacent vertex as the distance of the dequeued vertex plus one.
    • Enqueue the adjacent vertex into the queue.
• After the BFS is complete, the distance array will contain the shortest distances from the source vertex to all other vertices.
• Return the distance array.

Algorithm:

Function int[] shortestPath(int n, int[][] edges, int src):

1. Iterate over the edges and create the 'adjacencyList' for the graph.
2. Declare an empty integer queue ‘q’.
3. Push ‘src’ into the queue ‘q’.
4. Initialize an array 'distance' of size 'n' (number of vertices) and set all values to infinity except 'distance[src]' = 0.
5. Initialize an array 'visited' of size 'n' (number of vertices) and set all values to false except 'visited[src]' = true.
6. While the queue is not empty:
   1. Pop one element from ‘q’ and assign it to an integer variable ‘u’.
   2. For each unvisited vertex, ‘v’ in ‘adjacencyList[u]’:
      1. ‘visited[v]’=true
      2. ‘distance[v]’ = ‘distance[u]’+1
      3. Push ‘v’ into the queue ‘q’.
7. Return array ‘distance’.