El algoritmo de Johnson es una forma de encontrar el camino más corto entre todos los pares de vértices de un grafo dirigido disperso. Permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicial que elimina todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado. Su nombre viene de Donald B.

rdfs:comment
  • El algoritmo de Johnson es una forma de encontrar el camino más corto entre todos los pares de vértices de un grafo dirigido disperso. Permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicial que elimina todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado. Su nombre viene de Donald B. (es)
foaf:isPrimaryTopicOf
rdfs:label
  • Algoritmo de Johnson (es)
Is foaf:primaryTopic of
dcterms:subject
prov:wasDerivedFrom
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 2531351 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 9326 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 30 (xsd:integer)
Is dbpedia-owl:wikiPageRedirects of
dbpedia-owl:wikiPageRevisionID
  • 76441853 (xsd:integer)
dbpedia-owl:wikiPageWikiLink [21 values]
Is dbpedia-owl:wikiPageWikiLink of