Distància (teoria de grafs)

En teoria de grafs, la distància entre els dos vèrtexs d'un graf és el nombre d'arestes en el camí més curt que els uneix. Això també es coneix com a distància geodèsica. Hi pot haver més d'un camí més curt entre dos vèrtexs. Si no hi ha cap camí que uneixi els dos vèrtexs, per exemple perquè pertanyen a diferents components, per convenció es diu que la distància entre ells és infinita.

En el cas d'un graf dirigit la distància $d(u,v)$ entre els dos vèrtexs $u$ i $v$ es defineix com la longitud del camí més curt des de $u$ fins a $v$ consistent en arcs, sempre que existeixi un camí. En contrast amb els grafs no dirigits, $d(u,v)$ i $d(v,u)$ poden no coincidir o fins i tot pot ser que una de les dues estigui definida i l'altra no.