Back to Course

Algorithm

0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
    Stacks
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 35 of 43
In Progress

All Pairs Shortest Paths

  1. In all pair shortest path, when a weighted graph is represented by its weight matrix W then objective is to find the distance between every pair of nodes.
  2. We will apply dynamic programming to solve the all pairs shortest path.
  3. In all pair shortest path algorithm, we first decomposed the given problem into sub problems.
  4. In this principle of optimally is used for solving the problem.
  5. It means any sub path of shortest path is a shortest path between the end nodes.

Steps:

i. Let A^k i,j be the length of shortest path from node i to node j such that the label for every intermediate node will be ≤ k.

ii. Now, divide the path from i node to j node for every intermediate node, say ‘k’ then there arises two case.

a. Path going from i to j via k.

b. Path which is not going via k.

iii. Select only shortest path from two cases.

iv. Using recursive method we compute shortest path.

v. Initially: 

KodNest Capture16

vi. Next computations:

KodNest Capture17
KodNest Capture18

Algorithm:

Analysis of Algorithm:

i. The first double for loop takes O (n2) time.

ii. The nested three for loop takes O (n3) time.

iii. Thus, the whole algorithm takes O (n3) time.

Example: Compute all pair shortest path for following figure 1.

KodNest Capture19
figure 1

Solution:

KodNest Capture20

Thus the shortest distances between all pair are obtained.

New Report

Close