Floyd–Warshall algorithm

Summary

In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation R, or (in connection with the Schulze voting system) widest paths between all pairs of vertices in a weighted graph. History and naming The Floyd–Warshall algorithm is an example of dynamic programming, and was published in its currently recognized form by Robert Floyd in 1962. However, it is essentially the sa

Official source

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (5)

Related publications

Related people

Related units

Related concepts (5)

Related concepts

Related courses (4)

Introduction to major operations research models and optimization algorithms

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems.

Ce cours approfondit les connaissances en programmation présentées dans le cours ICC du 1er semestre. L'accent est mis sur l'approche «orientée objet» (en C++), la conception et la spécification de programmes via la réalisation d'une mini-application dans un projet réalisé par binôme.

Related courses

Related lectures (8)

Related lectures

HTPCP: GNSS-R multi-channel correlation waveforms post-process solution for GOLD-RTR Instrument

David Atienza Alonso, Yi Guo

Global navigation satellite system reflectometry (GNSS-R) remote sensing is a new remote sensing technique of satellite navigation application. Essentially, it entails a method of remote sensing that receives and processes microwave signals reflected from various surfaces to extract useful information about those surfaces. The GPS open-loop differential real-time receiver (GOLD-RTR) instrument was designed by the ICE (IEEC-CSIC)1 to gather global positioning satellite system signals after they have been reflected from suitable surfaces (e.g. sea, ice and ground). In this paper, the problem of real-time postprocessing design is addressed in order to process the multichannel cross correlations waveform. This work is to realize real time single correlation integration algorithm (SCI) on the proposed novel platform, named as Heterogeneous Transmission and Parallel Computing Platform (HTPCP). The numerical results show that system throughput can reach up to about 1.669MB/sec. Comparing with the state-of-the-art serial SW solution, the processing time of SCI algorithm can improve about 19%. The coherent integration time can improve 8.17 times comparing with the conventional Symmetric Multiprocessing (SMP). And the parallel computing speed of HTPCP outperforms SMP.

IEEE Press2010

Conventional fluid flow estimation methods for in vivo optical microscopy are limited to two-dimensions and are only able to estimate the components of flow parallel to the imaging plane. This limits the study of flow in more intricate biological structures, such as the embryonic zebrafish heart, where flow is three-dimensional. To measure three-dimensional blood flow, we propose an algorithm to reconstruct a 3D, divergence-free flow map from multiple 2D flow estimates computed from image stacks captured from different views. This allows us to estimate the out-of-plane velocity component that is normally lost with single-view imaging. This paper describes our 3D flow reconstruction algorithm, evaluates its performance on a simulated velocity field, and demonstrates its application to in vivo cardiac imaging within a live zebrafish larva.

2015

On the security of CS-Cipher

Serge Vaudenay

CS-Cipher is a block cipher which has been proposed at FSE 1998. It is a Markov cipher in which diffusion is performed by multipermutations. We first provide a formal treatment for differential, linear and truncated differential cryptanalysis, and we apply it to CS-Cipher in order to prove that there exists no good characteristic for these attacks. This holds under the approximation that all round keys of CS-Cipher are uniformly distributed and independent. For this we introduce some new techniques for counting active Sboxes in computational networks by the Floyd-Warshall algorithm.

1999