Algorithme de Bellman-Ford

Résumé

L'algorithme de Bellman-Ford, aussi appelé algorithme de Bellman–Ford–Moore, est un algorithme qui calcule des plus courts chemins depuis un sommet source donné dans un graphe orienté pondéré. Il porte le nom de ses inventeurs Richard Bellman et Lester Randolph Ford junior (publications en 1956 et 1958), et de Edward Forrest Moore qui le redécouvrit en 1959. Contrairement à l'algorithme de Dijkstra, l'algorithme de Bellman-Ford autorise la présence de certains arcs de poids négatif et permet de détecter l'existence d'un circuit absorbant, c'est-à-dire de poids total strictement négatif, accessible depuis le sommet source. La complexité de l'algorithme est en O(|S| |A|) où |S| est le nombre de sommets |A| est le nombre d'arcs. Description L'algorithme de Bellman-Ford calcule, étant donnés un graphe G = (S, A) sans cycle de poids négatif et un sommet source s \in S, un plus court chemin de s à c

Source officielle

https://fr.wikipedia.org/wiki/Algorithme_de_Bellman-Ford

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (3)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (5)

Concepts associés

Chargement

Cours associés (7)

Cours associés

Chargement

Séances de cours associées (19)

Séances de cours associées

Chargement

Reconstruction of images from noisy linear measurements is a core problem in image processing, for which convex optimization methods based on total variation (TV) minimization have been the long-standing state-of-the-art. We present an alternative probabilistic reconstruction procedure based on approximate message-passing, Scampi, which operates in the compressive regime, where the inverse imaging problem is underdetermined. While the proposed method is related to the recently proposed GrAMPA algorithm of Borgerding, Schniter, and Rangan, we further develop the probabilistic approach to compressive imaging by introducing an expectation-maximization learning of model parameters, making the Scampi robust to model uncertainties. Additionally, our numerical experiments indicate that Scampi can provide reconstruction performance superior to both GrAMPA as well as convex approaches to TV reconstruction. Finally, through exhaustive best-case experiments, we show that in many cases the maximal performance of both Scampi and convex TV can be quite close, even though the approaches are a prori distinct. The theoretical reasons for this correspondence remain an open question. Nevertheless, the proposed algorithm remains more practical, as it requires far less parameter tuning to perform optimally.

Iop Publishing Ltd2016

Chargement

A Multi Level Monte Carlo Algorithm for the Treatment of Geometrical and Operational Uncertainties in Internal and External Aerodynamics

Pénélope Leyland, Fabio Nobile, Michele Pisaroni

In this work we present an efficient Multi Level Monte Carlo (MLMC) algorithm capable of propagating operational uncertainties, due to atmospheric variability of external aerodynamics flows and geometrical uncertainties due to manufacturing tolerances and fatigue. The technique is tested on the NACA 0012 airfoil in transonic conditions and a two compression ramps hypersonic scramjet intake configuration. The efficiency of the proposed MLMC algorithm in terms of accuracy versus overall computational cost is compared to a standard MC method.

AIAA2016

Chargement

Faster Shortest-Path Algorithms for Planar Graphs

Monika Henzinger

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiring O(n4/3 log(nL)) time, where L is the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms.

1997

Chargement