Cette semaine, nous continuons à étudier les algorithmes de décomposition des graphes, mais maintenant pour les graphes dirigés.

Dans ce module, vous étudierez les algorithmes permettant de trouver les plus courts chemins dans les graphes. Ces algorithmes ont de nombreuses applications. Lorsque vous lancez une application de navigation sur votre smartphone, comme Google Maps ou Yandex.Navi, elle utilise ces algorithmes pour trouver l'itinéraire le plus rapide entre le travail et le domicile, entre le domicile et l'école, etc. Lorsque vous recherchez des billets d'avion, ces algorithmes sont utilisés pour trouver un itinéraire avec le minimum de changements d'avion. De manière inattendue, ces algorithmes peuvent également être utilisés pour déterminer la manière optimale d'effectuer des opérations de change, ce qui permet parfois de réaliser d'énormes bénéfices ! Nous couvrirons toutes ces applications, et vous apprendrez les algorithmes Breadth-First Search, Dijkstra's Algorithm et Bellman-Ford Algorithm. Ces algorithmes sont efficaces et jettent les bases d'algorithmes encore plus efficaces que vous apprendrez et mettrez en œuvre dans le cadre du projet Shortest Paths Capstone Project pour trouver les meilleurs itinéraires sur des cartes réelles de villes et de pays, trouver les distances entre les personnes dans les réseaux sociaux. Au final, vous serez en mesure de trouver efficacement les plus courts chemins dans n'importe quel graphe. Cette semaine, nous étudierons l'algorithme Breadth-First Search.

Cette semaine, nous continuons à étudier les plus courts chemins dans les graphes. Vous apprendrez l'algorithme de Dijkstra qui peut être appliqué pour trouver le chemin le plus court pour rentrer du travail. Vous apprendrez également l'algorithme de Bellman-Ford qui peut être appliqué de manière inattendue pour choisir la manière optimale d'échanger des devises. À la fin, vous serez capable de trouver efficacement les chemins les plus courts dans n'importe quel graphique.

Dans ce module, nous étudions le problème de l'arbre couvrant minimum. Nous aborderons deux algorithmes gourmands élégants pour ce problème : le premier est dû à Kruskal et utilise la structure de données des ensembles disjoints, le second est dû à Prim et utilise la structure de données de la file d'attente prioritaire. Dans le devoir de programmation de ce module, vous calculerez une manière optimale de construire des routes entre les villes et une manière optimale de partitionner un ensemble donné d'objets en grappes (un problème fondamental dans l'exploration de données).

Dans ce module, vous apprendrez les algorithmes avancés des plus courts chemins qui fonctionnent en pratique des milliers (jusqu'à 25 000) de fois plus vite que l'algorithme classique de Dijkstra sur des réseaux routiers et des graphes de réseaux sociaux du monde réel. Vous travaillerez sur un projet de programmation basé sur ces algorithmes. Vous trouverez les chemins les plus courts sur les cartes réelles de certaines régions des États-Unis et les chemins les plus courts reliant les personnes dans les réseaux sociaux. Nous vous encourageons non seulement à utiliser les idées des cours de ce module dans vos implémentations, mais aussi à trouver vos propres idées pour accélérer l'algorithme ! Nous vous encourageons à vous affronter sur les forums pour voir quelle implémentation est la plus rapide :)