Dans un graphe orienté (digraphe), les arêtes ont une direction (A → B ≠ B → A). Dans un graphe pondéré, chaque arête porte un (distance, temps, capacité). La combinaison des deux modélise des systèmes réels où les relations sont unidirectionnelles et ont un coût.
Weighted directed graph:
A --5--> B
A --2--> C
C --1--> B
Adjacency list with weights:
A: [(B,5), (C,2)]
B: []
C: [(B,1)]
graph = {
'A': [('B', 5), ('C', 2)], # directed, weighted edges
'B': [],
'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
| Domaine | Sommets | Arêtes orientées pondérées |
|---|---|---|
| Cartes / GPS | intersections | routes à sens unique + temps de parcours |
| Réseaux | routeurs | liens + latence/bande passante |
| Planification de tâches | tâches | dépendances + durées |
| Finance | devises | taux de change |
| Objectif | Algorithme | Complexité |
|---|---|---|
| Chemin le plus court (poids non négatifs) | Dijkstra | O((V+E) log V) |
| Chemin le plus court (arêtes négatives) | Bellman-Ford | O(VE) |
| Tri avec dépendances | Tri topologique | O(V+E) |
| Détecter les cycles / accessibilité | DFS | O(V+E) |
L'orientation et le poids sont ce qui transforment un graphe abstrait en un modèle fidèle des problèmes de routage, de planification et de dépendances qui animent les applications réelles.
Le choix de l'algorithme dépend de ces propriétés — par exemple, les poids négatifs excluent Dijkstra et nécessitent Bellman-Ford.