Problema del camí més curt

Exemple de Graf Ponderat

En teoria de grafs, el problema del camí més curt consisteix a trobar un camí entre dos vèrtexs (o nodes) d'un graf de tal manera que la suma dels pesos de les arestes que el formen sigui mínima. Un exemple és trobar el camí més ràpid per anar d'una ciutat a una altra en un mapa. En aquest cas, els vèrtexs representen les ciutats i les arestes, les carreteres que les uneixen; la ponderació ve donada pel temps que s'empra en viatjar.

Introducció

Formalment, donat un graf ponderat (que és un conjunt V de vèrtexs, un conjunt E d'arestes i una funció de variable real ponderada f: E → R) i un element v ∈ V troba un camí P de v a v' ∈ V, tal que: $\sum _{p\in P}f(p)$ és el mínim entre tots els camins que connecten v i v'.

Aquest problema també és conegut com a problema dels camins més curts entre dos nodes, per diferenciar-lo de la següent generalització:

• El problema dels camins més curts des d'un origen en el qual hem de trobar els camins més curts d'un vèrtex origen v a tots els altres vèrtexs del graf.
• El problema dels camins més curts amb un destí en el qual hem de trobar els camins més curts des de tots els vèrtexs del graf a un únic vèrtex destí, això pot ser reduït al problema anterior invertint l'ordre.
• El problema dels camins més curts entre tots els parells de vèrtexs, en el qual hem de trobar els camins més curts entre cada parell de vèrtexs (v, v') al graf.

Algorismes

Els algorismes més importants per resoldre aquest problema són:

• Algorisme de Dijkstra, resol el problema dels camins més curts entre dos vèrtexs, des d'un origen i un únic destí.
• Algorisme de Bellman-Ford, resol el problema dels camins més curts des d'un origen si la ponderació de les arestes és negativa.
• Algorisme de Cerca A *, resol el problema dels camins més curts entre un parell de vèrtexs utilitzant l'heurística per intentar agilitzar la cerca.
• Algorisme de Floyd-Warshall, resol el problema dels camins més curts entre tots els vèrtexs.
• Algorisme de Johnson, resol el problema dels camins més curts entre tots els vèrtexs i pot ser més ràpid que el de Floyd-Warshall en grafs de baixa densitat.
• Teoria pertorbacional, troba en el pitjor dels casos el camí més curt a nivell local.

Aplicacions

Els algorismes dels camins més curts s'apliquen per trobar adreces de forma automàtica entre localitzacions físiques, com ara adreces en mapes de carrers.

Si un algorisme representa una màquina abstracta no determinista com un graf, on els vèrtexs descriuen estats, i les arestes possibles transicions, l'algorisme dels camins més curts es fa servir per trobar una seqüència òptima d'opcions per arribar a un cert estat final o per establir límits més baixos en el temps, necessari per aconseguir un estat donat. Per exemple, si els vèrtexs representen els estats d'un trencaclosques com el Cub de Rubik, cada aresta dirigida correspon a un simple moviment o gir. L'algorisme dels camins més curts es fa servir per trobar la solució que fa servir el mínim nombre possible de moviments.

En l'argot de les telecomunicacions, aquest algorisme també és conegut com el problema del mínim retard, i sovint es compara amb el problema dels camins més amples. Una aplicació més col·loquial és la teoria dels "Sis graus de separació", a partir de la qual s'intenta trobar el camí més curt entre dues persones qualssevol. Altres aplicacions inclouen la Investigació d'operacions, instal·lacions i facilitat de disseny, robòtica, transport i el disseny de circuits integrat a molt gran escala (VLSI).

Problemes relacionats

El problema de viatjant de comerç és el problema que tracta de trobar el camí més curt que passa només un cop per cada vèrtex i torna al començament. A diferència dels camins més curts, que pot ser resolt en un temps polinòmic en grafs sense cicles negatius, aquest problema és NP-complet, i com a tal, no té una resolució eficient (vegeu P = Problema NP). El problema de trobar el camí més llarg també és NP-complet.

Enllaços externs

• Camins més curts - Dr JBHayet
• Camins més curts des d'un origen a moltes destinacions - Juli Cèsar López Arxivat 2007-06-26 a Wayback Machine.
• Àlgebra matricial i Teoria de grafs - Luis M. Torres
• Demostració de l'Algorisme de Dijkstra
• Demostracion de l'Algorisme de Bellman Ford Arxivat 2010-03-26 a Wayback Machine.
• Exemple d'Exercici de Bellman Ford Arxivat 2009-06-17 a Wayback Machine.