Skip to content
EngineeringHulk

EngineeringHulk

Free Educational Notes

  • Home
  • Question Papers
  • Toggle search form
  • Mass of electron
    Mass of electron general
  • National Institute of Technology- NIT
    National Institute of Technology- NIT general
  • SSC-CHSL
    SSC CHSL full form general
  • IIT BOMBAY
    IIT full form – IIT Colleges general
  • ed full form
    ed full form general
  • Kranz anatomy
    Kranz Anatomy general
  • MBBS full form
    MBBS full form general
  • Domains of AI (Artificial Intelligence)
    Domains of AI (Artificial Intelligence) general
Floyd Algorithm

Floyd Algorithm

Posted on December 28, 2022December 28, 2022 By Dr. Jennifer Russel

Table of Contents

  • How Does The Floyd Algorithm Work?
  • The Use And Applications Of The Floyd Algorithm
  • Conclusion

Floyd algorithm finds the shortest paths in a weighted graph with positive or negative edge weights. It can also detect negative cycles. 

The algorithm works by starting at a given vertex and then using a relaxation technique to gradually find the shortest path between that vertex and all other vertices in the graph. The relaxation step works by considering each edge in the graph and updating the cost associated with each vertex if a shorter path is found.

When all edges have been considered, the shortest paths between the given vertex and all other vertices will have been found. The algorithm can then be repeated for all other vertices in the graph to find the shortest paths between any two vertices.

It is important to note that Floyd’s algorithm can only be used on graphs with positive or negative edge weights. If any of the edge weights are zero, then the algorithm will not work as expected.

How Does The Floyd Algorithm Work?

The algorithm works by iteratively computing the shortest path from each node to every other node using the “relaxation” technique. The algorithm is capable of handling both directed and undirected graphs, as well as mixed graphs containing both positive and negative weights.

In each iteration, the algorithm relaxes all edges that could lead to a shorter path. This process is repeated until no further relaxation is possible and the shortest paths between all pairs of nodes have been determined.

The Floyd algorithm is widely used in network routing protocols and for solving the All-Pairs Shortest Paths (APSP) problem. It is also used in various applications such as finding the transitive closure of a relation, constructing shortest-path spanning trees, and computing the distance matrix of a graph.

The algorithm works by iteratively relaxing the shortest path estimates between all pairs of vertices in the graph. Specifically, it maintains a distance matrix D, where D [i] [j] is the shortest distance from vertex i to vertex j. 

The algorithm repeatedly updates this matrix by considering all pairs of vertices (i, j) and checking if there is a path from i to j that is shorter than the current shortest path estimate. If such a path exists, the algorithm updates the distance estimate for the pair (i, j) accordingly.

The algorithm has a time complexity of O(n^3), where n is the number of vertices in the graph. This makes it suitable for use on dense graphs, but not on very large charts or graphs with a high number of edges.

Here is some pseudocode for the Floyd algorithm:

function floyd(graph):

  n = len(graph)

  D = copy(graph)  # Initialize distance matrix with the graph

  for k in range(n):

    for i in range(n):

      for j in range(n):

        D[i][j] = min(D[i][j], D[i][k] + D[k][j])  # Relax the shortest path estimate

  return D

This pseudocode assumes that the input graph is represented as an adjacency matrix, where graph [i] [j] is the weight of the edge from vertex i to vertex j, or infinity if there is no such edge. The function returns the distance matrix D, where D [i] [j] is the shortest distance from vertex i to vertex j.

Certainly! Here is a simple example of the Floyd algorithm on a small graph with three vertices:

A —– B

  |       |

5|       | 2

  |       |

C —– D

      3

To find the shortest paths between all pairs of vertices in this graph, we can use the following steps:

Initialize the distance matrix D with the graph itself. We can represent the graph as an adjacency matrix as follows:

D = [[0, 5, INF],

       [INF, 0, 2],

     [INF, INF, 0]]

Here, INF represents infinity, and 0 represents the fact that there is no distance between a vertex and itself.

Iterate over all pairs of vertices (i, j) and check if there is a path from i to j that is shorter than the current shortest path estimate. Specifically, we check if D[i][j] > D[i][k] + D[k][j] for any intermediate vertex k. If such a path exists, we update the distance estimate for the pair (i, j) accordingly.

For example, in the first iteration, we consider the pair (A, C). We check if there is a shorter path from A to C via an intermediate vertex B. Since D[A][C] = INF and D[A][B] + D[B][C] = 5 + 2 = 7, we update D[A][C] to be equal to D[A][B] + D[B][C] = 7.

We continue this process until we have considered all pairs of vertices. After all iterations, the distance matrix D will contain the shortest distance between all pairs of vertices in the graph:

D = [[0, 5, 7],

      [INF, 0, 2],

    [INF, INF, 0]]

I hope this example helps to clarify how the Floyd algorithm works.

The Use And Applications Of The Floyd Algorithm

The Floyd algorithm is a general-purpose algorithm for finding the shortest paths in a weighted graph. It can be used in a variety of applications where it is important to find the shortest path between two vertices in a graph, such as:

Floyd Algorithm
  • Network routing: The Floyd algorithm can be used to find the shortest path between two nodes in a communication network, such as a computer network or a transportation network.
  • Map routing: The Floyd algorithm can be used to find the shortest path between two points on a map, taking into account factors such as road distance and traffic.
  • Project scheduling: The Floyd algorithm can be used to find the shortest path through a project network, taking into account the dependencies between tasks and the time required to complete each task.
  • Data compression: The Floyd algorithm can be used to find the shortest path through a tree data structure, which can be used to compress data.
  • Social network analysis: The Floyd algorithm can be used to find the shortest path between two individuals in a social network, taking into account the relationships between individuals.

These are just a few examples of the many possible applications of the Floyd algorithm.

Conclusion

In conclusion, the Floyd algorithm is a useful tool for finding the shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). It works by iteratively relaxing the shortest path estimates between all pairs of vertices in the graph, and has a time complexity of O(n^3), where n is the number of vertices in the graph.

This makes it suitable for use on dense graphs but not on very large charts or graphs with a high number of edges. The Floyd algorithm has a wide range of applications, including network routing, map routing, project scheduling, data compression, and social network analysis. I hope this summary helps to clarify the main points about the Floyd algorithm.

Also, see Types of CSS

general

Post navigation

Previous Post: Microprogramming
Next Post: Operating System Functions

Related Posts

  • udemy course
    Top 10 Udemy Courses general
  • UPSC preparation
    UPSC Syllabus general
  • xnxp personality traits
    XNXP personality traits general
  • Classification of computer
    Classification of computer general
  • SSC-CHSL
    SSC CHSL full form general
  • Lattice and Recurrence Relation
    Lattice and Recurrence Relation general

Categories

  • Automobile Engineering (29)
    • Module 1 (10)
      • Clutch (2)
      • Propellar Shaft & Axle (2)
      • Transmission (6)
    • Module 2 (10)
      • Braking System (5)
      • Final Drive and Differential (2)
      • Steering System (3)
    • Module 3 (2)
      • Suspension System (1)
      • Wheels & Tyres (1)
    • Module 4 (6)
      • Automotive Electrical System (6)
  • general (137)
  • Manufacturing Engineering/Production Process (11)
  • News (1)
  • Renewable sources of Energy (34)
    • Energy from Biomass (7)
    • Geothermal Energy (6)
    • Solar Energy (1)
    • Wind Energy (3)
  • Thermodynamics (6)

    Recent Posts

    • Thyristor in power electronics March 25, 2023
    • ibps (Institute of Banking Personnel Selection) March 25, 2023
    • Layers of atmosphere March 25, 2023
    • 1 million in lakhs March 24, 2023
    • Who discovered proton March 24, 2023
    • SIM full form March 24, 2023
    • Assam capital March 24, 2023
    • Income tax inspector March 24, 2023
    • Isomers of pentane March 24, 2023
    • Classification of computer March 22, 2023
    • IAS full form March 22, 2023
    • VISA full form March 21, 2023
    • trysem full form March 21, 2023
    • Savinay Avagya Andolan March 21, 2023
    • Marcos commando March 21, 2023
    • Hokera wetland March 21, 2023
    • Nose Shapes: Exploring the Fascinating World March 21, 2023
    • Indian football players March 19, 2023
    • Nivedita Menon March 19, 2023
    • The Fastest Century in T20: A Record That Continues to Impress March 19, 2023
    • Lachit Borphukan March 18, 2023
    • XNXP personality traits March 18, 2023
    • how many countries in the world? March 18, 2023
    • gk questions March 18, 2023
    • Vera Gedroits March 17, 2023
    • H3N2 virus – Detailed important information March 14, 2023
    • Nut vs bolt March 12, 2023
    • Specific gravity of water March 12, 2023
    • Vernier caliper March 3, 2023
    • Lami’s theorem March 1, 2023
    • lad meaning in Hindi March 1, 2023
    • Byopia/biopia March 1, 2023
    • Top 10 Udemy Courses March 1, 2023
    • Mass of electron February 28, 2023
    • Hcl Molar Mass February 17, 2023
    • Vikram University February 17, 2023
    • District education office February 17, 2023
    • Agriculture officer February 17, 2023
    • Loco Pilot February 16, 2023
    • Google bard AI February 8, 2023
    • Remote procedure call [RPC] February 8, 2023
    • Raj Rishi Bhartrihari Matsya University February 8, 2023
    • CCC full form: Course on computer concepts February 8, 2023
    •  Maharaja Krishnakumar Sinhji Bhavnagar University February 8, 2023
    • Scholarship 2.0 February 8, 2023
    • Amyloidosis: Causes, Risk Factors, diagnosis & treatment February 5, 2023
    • Type 1 and Type 2 Superconductors February 4, 2023
    • N phenylethanamide February 4, 2023
    • Two nation theory February 4, 2023
    • Kranz Anatomy February 4, 2023
    • Megasporogenesis February 4, 2023
    • NADPH full form February 4, 2023
    • Unit of hall coefficient February 4, 2023
    • Fixed beam February 4, 2023
    • History of Pharmacognosy February 4, 2023
    • Unit of Strain February 4, 2023
    • Sarasvati Shishu Vidya mandir February 2, 2023
    • Tally full form February 2, 2023
    • IDR full form February 2, 2023
    • SSC CHSL full form February 1, 2023
    • geothermal energy
      Advantages, disadvantages & application of geothermal energy Geothermal Energy
    • 11th admission
      11th Admission general
    • 30000 in Words
      30000 in Words general
    • Microprogramming
      Microprogramming general
    • BSF Head Constable Ministerial Exam Syllabus
      BSF Head Constable Ministerial Exam Syllabus general
    • enginnering hulk
      What are the Materials and Alloys used in Workshop? Manufacturing Engineering/Production Process
    • visa full form
      VISA full form general
    • type 1 and type 2 superconductors
      Type 1 and Type 2 Superconductors general

    Privacy Policy

    Cookie Policy

    About us

    Contact us

    Copyright © 2023 EngineeringHulk.

    Powered by PressBook News WordPress theme

    WhatsApp me