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

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