Séance de cours

L'algorithme de Dijkstra et le 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.

Dans cours

MATH-261: Discrete optimization

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. ...

Description

Cette séance de cours couvre l'algorithme de Dijkstra pour le problème du chemin le plus court ALL-TO-ONE, en le combinant avec Bellman-Ford pour un algorithme de chemin le plus court ALL-PAIRS efficace. Les diapositives détaillent les étapes de l'algorithme de Dijkstra, l'importance des bords non négatifs et le processus de recherche de la solution optimale. Il explore également le concept d'algorithmes ALL-TO-ONE et ALL-PAIRS, en discutant des implications des coûts de périphérie négatifs et de l'importance de l'exécution de Dijkstra plusieurs fois. La séance de cours se termine par un ensemble de problèmes pratiques impliquant l'application des algorithmes pour trouver des solutions optimales pour divers scénarios.

Enseignant·e·s (2)

Friedrich Eisenbrand

Enseignement et PhD Doctorant·es actuel·les Ruben Manuel Skorupinski, Neta Singer, Lukas Vogl, Jiaye Wei A dirigé les thèses EPFL de Thomas Rothvoss, Nicolai Hähnle, Martin Niemeier, Adrian Aloysius Bock, Carsten Moldenhauer, Alfonso Bolívar Cevallos Manzano, Manuel Francesco Aprile, Igor Malinovic, Christoph Hunkenschröder, Moritz Andreas Venzin, Jana Tabea Cslovjecsek A co-dirigé les thèses EPFL de Puck van Gerwen Cours Algèbre linéaire avancée II - diagonalisation MATH-115(a) L'objectif

Rom Pinchasi

Enseignement et PhD Cours The Maths of Puzzles MATH-704

Source officielle

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Concepts associés (32)

Chaîne (théorie des graphes)

Dans un graphe non orienté, une chaîne reliant à , notée , est définie par une suite finie d'arêtes consécutives, reliant à . La notion correspondante dans les graphes orientés est celle de chemin. Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts. Une chaîne simple est une chaîne ne passant pas deux fois par une même arête, c'est-à-dire dont toutes les arêtes sont distinctes. Un cycle est une chaîne simple dont les deux extrémités sont identiques.

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

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.

Afficher plus

Séances de cours associées (64)

Arbres d'éclaboussure minimum: Algorithme de Prim

Explore l'algorithme de Prim pour les arbres à portée minimale et introduit le problème Traveling Salesman.

Algorithmes graphiques II: Traversée et chemins

Explore les méthodes de traversée des graphes, les arbres couvrants et les chemins les plus courts en utilisant BFS et DFS.

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.

Introduction au chemin le plus court

Présente le concept de chemin le plus court, discutant des chemins pondérés, des chemins hamiltoniens et des algorithmes d'optimisation de chemin.

Programmation dynamique : Algorithmes des voies les plus courtes

Explore les stratégies de programmation dynamiques pour trouver des chemins les plus courts dans les réseaux avec divers algorithmes et complexités.

Afficher plus

Concepts associés (32)

Chaîne (théorie des graphes)

Théorie des graphes

Lexique de la théorie des graphes

Connectivity (graph theory)

Algorithme de Dijkstra

Afficher plus