Problema del camí més curt

Archiu:Shortest path with direct weights.svg

Problema del camí més curt

Archiu:Caminosmascortos.jpg

Eixemple de Grafo Ponderat

En la teoria de grafos, el problema del camí més curt és el problema que consistix en trobar un camí entre dos vèrtiços o nodos, de tal manera que la suma dels pesos de les arestes que ho constituïxen siga mínima. Al camí més curt entre dos vèrtiços també se li coneix com a geodèsica.

Este problema no necessàriament té una única solució. Ademés, té diverses aplicacions. Un eixemple és trobar el camí més ràpit per a anar d'una ciutat a una atra en un mapa. En este cas, els vèrtiços representarien les ciutats i les arestes les carreteres que les unixen, la ponderació de les quals ve donada pel temps que s'ampra en travessar-les.

Definicions

El problema del camí més curt pot ser definit para grafos no dirigits o dirigits. La següent és una definició per a grafos no dirigits, en el cas de grafos dirigits la definició de camí requerix que els vèrtiços adjacents estiguen conectats per una apropiada aresta dirigida.

Dos vèrtiços són adjacents quan posseïxen una aresta comuna. Un camí en un grafo no dirigit és una seqüència de vèrtiços $P=(v_1,v_2,\dots ,v_n)\in V\times V\times \dots \times V$ tal que tot vèrtiç $v_i$ és adjacent en el vèrtiç $v_{i+1}$. Un camí $P$ es diu que és de llongitut $n-1$ si va des de $v_1$ fins a $v_n$.

Siga $e_{i,j}$ l'aresta incident en els vèrtiços $v_i$ i $v_j$. Donada una funció de variable real ponderada $f:E\to ℝ$ i un grafo no dirigit $G$, el camí més curt des de $v$ fins a $v^{\prime }$ és el camí $P=(v_1,v_2,\dots ,v_n)$ (a on $v_1=v$ i $v_n=v^{\prime }$) sobre tots els possibles $n$ que minimisa la suma $\sum _{i=1}^{n-1}f(e_{i,i+1}).$ Quan cada aresta en el grafo té un pes unitari o $f:E\to \{1\}$, trobar el camí més curt és equivalent a trobar el camí en menor número d'arestes.

El problema és també conegut com el problema dels camins més curts entre dos nodos, per a diferenciar-ho de les següents generalisacions:

• El problema dels camins més curts des d'un orige, en el qual tenim que trobar els camins més curts d'un vèrtiç orige v a tots els demés vèrtiços del grafo.
• El problema dels camins més curts en un destí, en el qual tenim que trobar els camins més curts des de tots els vèrtiços del grafo a un únic vèrtiç destine, açò pot ser reduït al problema anterior invertint l'orde.
• El problema dels camins més curts entre tots els parells de vèrtiços, el qual tenim que trobar els camins més curts entre cada parell de vèrtiços (v, v') en el grafo.

La distància geodèsica o simplement distancia entre dos vèrtiços és la llongitut del camí més curt o geodèsica entre ells. La distància entre dos vèrtiços $i$ i $j$ es pot denotar com $d(i,j)$; en tal cas, note que $d(i,j)=d(j,i)$. Si dos vèrtiços no són accessibles a través d'un camí, llavors la distància entre ells és infinita.

Algoritmes

Els algoritmes més importants per a resoldre este problema són:

• Algoritme de Dijkstra, resol el problema dels camins més curts des d'un únic vèrtiç orige fins a tots els atres vèrtiços del grafo.
• Algoritme de Bellman - Ford, resol el problema dels camins més curts des d'un orige si la ponderació de les arestes és negativa.
• Algoritme de Busca A*, resol el problema dels camins més curts entre un parell de vèrtiços usant la heurística per a intentar agilitar la busca.

• Algoritme de Floyd - Warshall, resol el problema dels camins més curts entre tots els vèrtiços.
• Algoritme de Johnson, resol el problema dels camins més curts entre tots els vèrtiços i pot ser més ràpit que el de Floyd-Warshall en grafos de baixa densitat.
• Algoritme de Viterbi, resol el problema del camí estocàstic més curt en un pes provabilístic adicional en cada vèrtiç.

Anex: Eixemple d'Algoritme de Bellman - Ford

Atres algoritmes i evaluacions associades poden es trobades en l'artícul de Cherkassky et al.

Vore també

• Busca de ruta
• Problema del viajante
• IEEE 802.1aq
• Ret de fluix
• Llínea geodèsica
• Curves en secció de la Terra

Bibliografia

• Bellman, Richard (1958). “On a routing problem”. Quarterly of Applied Mathematics 16: 87–90.
• “A note on two problems in connexion with graphs” (1959). Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390.
• Cormen, Thomas H.. «Single-Source Shortest Paths and All-Pairs Shortest Paths», Introduction to Algorithms, 2 edició, MIT Press, pp. 580–642.
• “Fibonacci heaps and their uses in improved network optimization algorithms” (1987). Journal of the Association for Computing Machinery 34 (3): 596–615. doi:10.1145/28869.28874.
• (1957) Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems, Cleveland, Ohio: Case Institute of Technology.
• Shimbel, Alfonso (1953). “Structural parameters of communication networks”. Bulletin of Mathematical Biophysics 15 (4): 501–507. doi:10.1007/BF02476438.
• (2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.