---
# System prepended metadata

title: Théorie des graphes
tags: [cours, ' theorie des graphes']

---

---
tags: cours, theorie des graphes
author: Robin 'Pachichi' Boucher
date: 08/03/2019
title: Théorie des graphes
---
> 08/03/19

# Théorie des graphes
BFS -> carte des distances -> Dijkstra -> Bellman Ford

BFS: distmap(G=(V,E), ==s== $\in$ V) avec ==s==: source sans poids

```graphviz
digraph exemple
{
    rankdir=LR
    s -> {1,3}
    1 -> {2,3}
    2 -> 4
    3 -> {2,4}
    4 -> 2
}
```

Pseudo code pour remplir la liste des successeurs à parcourir:

>distmap(G=(V,E), s $\in$ V):
--  $\forall$ v $\in$ V, dist[v] = $\infty$
--  dist[s] = 0
--  todo = [s]
--  while todo $\neq$ []:
------    x = todo.pop_front()
------    for y $\in$ $\delta^+$(x):
----------      if (dist[y] == $\infty$):
------------      dist[y] <- dist[x] + 1
------------      todo.push_back(y)
--  return dist

<img src="https://cdn.discordapp.com/attachments/531854990051115009/553569932403671043/IMG_20190308_142745.jpg" />

++Dijkstra simplifié:++
entrée: graphe pondéré, avec poids positifs, s $\in$ V
sortie: dist[y] la distance entre s et y

<img src="https://cdn.discordapp.com/attachments/531854990051115009/553579435526324224/IMG_20190308_150620.jpg" />

++Algo de Ballman-Ford++