---
# System prepended metadata

title: Theorie des graphs 4
tags: [' ING1', theorie des graphs, ' S6']

---

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

```graphviz
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é