Problema del camí més curt

De Viquipèdia
Dreceres ràpides: navegació, cerca
Exemple de Graf Ponderat

A la Teoria de grafs, el problema dels camins més curts és el problema que consisteix a trobar un camí entre dos vèrtexs (o nodes) de tal manera que la suma dels pesos de les arestes que el constitueixen és 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 travessar.


Introducció[modifica | modifica el codi]

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 VAV ' ∈ V, tal que:


\sum_{p\in P}f (p)


és el mínim entre tots els camins que connecten vi v '.

El problema és també conegut com el problema dels camins més curts entre dos nodes, per diferenciar 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 va 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 , el qual hem de trobar els camins més curts entre cada parell de vèrtexs (v, v ') al graf.


Algorismes[modifica | modifica el codi]

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 a grafs de baixa densitat.
  • Teoria pertorbacional , troba en el pitjor dels casos el camí més curt a nivell local.
Llista de Exemple de Algorisme de Dijkstra [modifica | modifica el codi]
Llista de Exemple de Algorisme de Bellman - Ford [modifica | modifica el codi]

Aplicacions[modifica | modifica el codi]

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

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, a aquest algorisme és també 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 VLSI de disseny.

Problemes Relacionats[modifica | modifica el codi]

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 polinomial 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 és també NP-complet.

Enllaços externs[modifica | modifica el codi]