L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme per a la determinació del camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom serà el Edsger Dijkstra, qui el va descriure per primera vegada el 1959.

Property Value
dbo:abstract
  • L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme per a la determinació del camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom serà el Edsger Dijkstra, qui el va descriure per primera vegada el 1959. La idea subjacent en aquest algorisme consisteix a anar explorant tots els camins més curts que parteixen del vèrtex origen i que porten a tots els altres vèrtexs, quan s'obté el camí més curt des del vèrtex origen, a la resta de vèrtexs que formen el graf, l'algorisme s'atura. L'algorisme és una especialització de la cerca de cost uniforme, i com a tal, no funciona en grafs amb arestes de cost negatiu (l'hora de triar sempre el node amb distància menor, poden quedar exclosos de la cerca nodes que en properes iteracions baixarien el cost general del camí al passar per una aresta amb cost negatiu). (ca)
  • L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme per a la determinació del camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom serà el Edsger Dijkstra, qui el va descriure per primera vegada el 1959. La idea subjacent en aquest algorisme consisteix a anar explorant tots els camins més curts que parteixen del vèrtex origen i que porten a tots els altres vèrtexs, quan s'obté el camí més curt des del vèrtex origen, a la resta de vèrtexs que formen el graf, l'algorisme s'atura. L'algorisme és una especialització de la cerca de cost uniforme, i com a tal, no funciona en grafs amb arestes de cost negatiu (l'hora de triar sempre el node amb distància menor, poden quedar exclosos de la cerca nodes que en properes iteracions baixarien el cost general del camí al passar per una aresta amb cost negatiu). (ca)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 602713 (xsd:integer)
dbo:wikiPageRevisionID
  • 17583243 (xsd:integer)
dct:subject
rdfs:comment
  • L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme per a la determinació del camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom serà el Edsger Dijkstra, qui el va descriure per primera vegada el 1959. (ca)
  • L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme per a la determinació del camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom serà el Edsger Dijkstra, qui el va descriure per primera vegada el 1959. (ca)
rdfs:label
  • Algorisme de Dijkstra (ca)
  • Algorisme de Dijkstra (ca)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is foaf:primaryTopic of