Séance de cours

Algorithme du chemin le plus court

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours présente l'algorithme de chemin le plus court, qui met à jour les étiquettes en fonction des conditions d'optimalité pour trouver le chemin le plus court d'une seule origine à toutes les destinations. L'algorithme itère sur les nœuds, mettant à jour les étiquettes et détectant les cycles de coûts négatifs pour assurer l'optimalité.

Dans MOOC

Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Introduction au concept mathématique des réseaux et à deux importants problèmes d'optimisation sur les réseaux : le problème du transbordement et le problème du chemin le plus court. Brève introduction à la puissance de modélisation de l'optimisation discrète, avec référence à des problèmes classiques. Introduction à l'algorithme branch and bound et au concept de coupes.

Source officielle

Concepts associés (13)

Problème de plus court chemin

vignette|Exemple d'un plus court chemin du sommet A au sommet F : (A, C, E, D, F). En théorie des graphes, le 'problème de plus court chemin' est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. Il existe de nombreuses variantes de ce problème suivant que le graphe est fini, orienté ou non, que chaque arc ou arête possède ou non une valeur qui peut être un poids ou une longueur.

Réseau informatique

thumb|upright|Connecteurs RJ-45 servant à la connexion des réseaux informatiques via Ethernet. thumb|upright Un réseau informatique ( ou DCN) est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un (un réseau est un « petit rets », c'est-à-dire un petit filet), on appelle nœud l'extrémité d'une connexion, qui peut être une intersection de plusieurs connexions ou équipements (un ordinateur, un routeur, un concentrateur, un commutateur).

Topologie de réseau

vignette Une topologie de réseau informatique correspond à l'architecture (physique, logicielle ou logique) de celui-ci, définissant les liaisons entre les équipements du réseau et une hiérarchie éventuelle entre eux. Elle peut définir la façon dont les équipements sont interconnectés et la représentation spatiale du réseau (topologie physique). Elle peut aussi définir la façon dont les données transitent dans les lignes de communication (topologies logiques).

Algorithme de Dijkstra

En théorie des graphes, l'algorithme de Dijkstra (prononcé ) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.

Théorie des réseaux

vignette|Graphe partiel de l'internet, basé sur les données de opte.org du 15 janvier 2005 (voir description de l'image pour plus de détails) La théorie des réseaux est l'étude de graphes en tant que représentation d'une relation symétrique ou asymétrique entre des objets discrets. Elle s'inscrit dans la théorie des graphes : un réseau peut alors être défini comme étant un graphe où les nœuds (sommets) ou les arêtes (ou « arcs », lorsque le graphe est orienté) ont des attributs, comme une étiquette (tag).

Afficher plus

Séances de cours associées (34)

Chemin le plus court, algorithme de Dijkstra MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Explore l'algorithme de Dijkstra pour trouver le chemin le plus court dans un réseau avec des coûts non négatifs et des étiquettes permanentes.

Modèles de propagation épidémique

Couvre les modèles classiques de propagation et de dynamique épidémiques sur des réseaux avec des exemples.

Monte-Carlo Methods Quiz

Présente un quiz sur l'estimation des variables de retour dans les méthodes Monte-Carlo.

Programmation dynamique : le triangle de Pascal et l'algorithme de Floyd

Explore la programmation dynamique à travers le Triangle de Pascal et l'Algorithme de Floyd.

AutoCAD : Fonctions de base pour Vault Plan

Couvre les fonctions de base d'AutoCAD pour la création d'un plan de voûte, y compris les outils, les propriétés et les modifications paramétriques.

Afficher plus

Concepts associés (13)

Problème de plus court chemin

Réseau informatique

Topologie de réseau

Algorithme de Dijkstra

Théorie des réseaux

Afficher plus