---
lang: fr
tags: theorie des graphs, S6, ING1
title: Theorie des graphs 4
date: 08/03/2019
---

# Theorie des graphs 4

Programme du jour:
- BFS
- Carte de distances
- Dijkstra
- Bellman ford

distmap(G=(V, E), s $\in$ V)

digraph G {
rankdir = LR
s->{1,2}
1->2->4
1->3
3->4
3->2
4->2
}

Distance par rapport à s.
Les index correspondent au numéro du sommet.
Ex: dist[3] = distance entre le sommet s et 3
dist : |X|X|X|X|X|

todo = [0] : |0|$\infty$|$\infty$|$\infty$|$\infty$|
todo = [0] : |0|1|$\infty$|1|$\infty$|
todo = [0] : |0|1|2|1|$\infty$|

Algo en pseudo code:

theta(|V|) $\forall v \in V, dist[v] = \infty$
theta(1) $dist[s] = 0$
theta(1) $todo = [s]$
O(|V|) $while todo \ne [] :$
O(|V|) $\space \space x = todo.pop_front()$
$\space \space for \space y \in \gamma^+(x):$
O(|E|)$\space \space \space \space if \space dist[y] == \infty:$
O(|V|)$\space \space \space \space \space \space dist[y] \leftarrow dist[x] + 1$
O(|V|)$\space \space \space \space \space \space todo.push_back(y)$
$return dist$

Total = O(|V| + |E|)

Disjkstra simplifié