{"payload":{"allShortcutsEnabled":false,"path":"src/algorithms/graph/bellman-ford","repo":{"id":166421083,"defaultBranch":"master","name":"javascript-algorithms","ownerLogin":"zlanusic","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2019-01-18T14:55:47.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/1186208?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1631817692.992358","canEdit":false,"refType":"branch","currentOid":"f08fc37dad3f4e7d9dcceb8cdcbf07d89859d2ac"},"tree":{"items":[{"name":"__test__","path":"src/algorithms/graph/bellman-ford/__test__","contentType":"directory"},{"name":"README.md","path":"src/algorithms/graph/bellman-ford/README.md","contentType":"file"},{"name":"bellmanFord.js","path":"src/algorithms/graph/bellman-ford/bellmanFord.js","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.md","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eBellman–Ford Algorithm\u003c/h1\u003e\u003ca id=\"user-content-bellmanford-algorithm\" class=\"anchor\" aria-label=\"Permalink: Bellman–Ford Algorithm\" href=\"#bellmanford-algorithm\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe Bellman–Ford algorithm is an algorithm that computes shortest\npaths from a single source vertex to all of the other vertices\nin a weighted digraph. It is slower than Dijkstra's algorithm\nfor the same problem, but more versatile, as it is capable of\nhandling graphs in which some of the edge weights are negative\nnumbers.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/17b483d507f01ac4498dfbd2be496c10954639e2e9b89623eb978db2b2f6d8f3/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f322f32652f53686f72746573745f706174685f44696a6b737472615f76735f42656c6c6d616e466f72642e676966\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/17b483d507f01ac4498dfbd2be496c10954639e2e9b89623eb978db2b2f6d8f3/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f322f32652f53686f72746573745f706174685f44696a6b737472615f76735f42656c6c6d616e466f72642e676966\" alt=\"Bellman-Ford\" data-animated-image=\"\" data-canonical-src=\"https://upload.wikimedia.org/wikipedia/commons/2/2e/Shortest_path_Dijkstra_vs_BellmanFord.gif\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eComplexity\u003c/h2\u003e\u003ca id=\"user-content-complexity\" class=\"anchor\" aria-label=\"Permalink: Complexity\" href=\"#complexity\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWorst-case performance \u003ccode\u003eO(|V||E|)\u003c/code\u003e\nBest-case performance\t\u003ccode\u003eO(|E|)\u003c/code\u003e\nWorst-case space complexity \u003ccode\u003eO(|V|)\u003c/code\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eReferences\u003c/h2\u003e\u003ca id=\"user-content-references\" class=\"anchor\" aria-label=\"Permalink: References\" href=\"#references\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm\" rel=\"nofollow\"\u003eWikipedia\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.youtube.com/watch?v=obWXjtg0L64\u0026amp;list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8\" rel=\"nofollow\"\u003eOn YouTube by Michael Sambol\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Bellman–Ford Algorithm","anchor":"bellmanford-algorithm","htmlText":"Bellman–Ford Algorithm"},{"level":2,"text":"Complexity","anchor":"complexity","htmlText":"Complexity"},{"level":2,"text":"References","anchor":"references","htmlText":"References"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fzlanusic%2Fjavascript-algorithms%2Ftree%2Fmaster%2Fsrc%2Falgorithms%2Fgraph%2Fbellman-ford"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"src/algorithms/graph":{"items":[{"name":"articulation-points","path":"src/algorithms/graph/articulation-points","contentType":"directory"},{"name":"bellman-ford","path":"src/algorithms/graph/bellman-ford","contentType":"directory"},{"name":"breadth-first-search","path":"src/algorithms/graph/breadth-first-search","contentType":"directory"},{"name":"bridges","path":"src/algorithms/graph/bridges","contentType":"directory"},{"name":"depth-first-search","path":"src/algorithms/graph/depth-first-search","contentType":"directory"},{"name":"detect-cycle","path":"src/algorithms/graph/detect-cycle","contentType":"directory"},{"name":"dijkstra","path":"src/algorithms/graph/dijkstra","contentType":"directory"},{"name":"eulerian-path","path":"src/algorithms/graph/eulerian-path","contentType":"directory"},{"name":"floyd-warshall","path":"src/algorithms/graph/floyd-warshall","contentType":"directory"},{"name":"hamiltonian-cycle","path":"src/algorithms/graph/hamiltonian-cycle","contentType":"directory"},{"name":"kruskal","path":"src/algorithms/graph/kruskal","contentType":"directory"},{"name":"prim","path":"src/algorithms/graph/prim","contentType":"directory"},{"name":"strongly-connected-components","path":"src/algorithms/graph/strongly-connected-components","contentType":"directory"},{"name":"topological-sorting","path":"src/algorithms/graph/topological-sorting","contentType":"directory"},{"name":"travelling-salesman","path":"src/algorithms/graph/travelling-salesman","contentType":"directory"}],"totalCount":15},"src/algorithms":{"items":[{"name":"cryptography","path":"src/algorithms/cryptography","contentType":"directory"},{"name":"graph","path":"src/algorithms/graph","contentType":"directory"},{"name":"linked-list","path":"src/algorithms/linked-list","contentType":"directory"},{"name":"math","path":"src/algorithms/math","contentType":"directory"},{"name":"search","path":"src/algorithms/search","contentType":"directory"},{"name":"sets","path":"src/algorithms/sets","contentType":"directory"},{"name":"sorting","path":"src/algorithms/sorting","contentType":"directory"},{"name":"string","path":"src/algorithms/string","contentType":"directory"},{"name":"tree","path":"src/algorithms/tree","contentType":"directory"},{"name":"uncategorized","path":"src/algorithms/uncategorized","contentType":"directory"}],"totalCount":10},"src":{"items":[{"name":"algorithms","path":"src/algorithms","contentType":"directory"},{"name":"data-structures","path":"src/data-structures","contentType":"directory"},{"name":"playground","path":"src/playground","contentType":"directory"},{"name":"utils","path":"src/utils","contentType":"directory"}],"totalCount":4},"":{"items":[{"name":"assets","path":"assets","contentType":"directory"},{"name":"src","path":"src","contentType":"directory"},{"name":".babelrc","path":".babelrc","contentType":"file"},{"name":".editorconfig","path":".editorconfig","contentType":"file"},{"name":".eslintrc","path":".eslintrc","contentType":"file"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"CODE_OF_CONDUCT.md","path":"CODE_OF_CONDUCT.md","contentType":"file"},{"name":"CONTRIBUTING.md","path":"CONTRIBUTING.md","contentType":"file"},{"name":"LICENSE","path":"LICENSE","contentType":"file"},{"name":"README.es-ES.md","path":"README.es-ES.md","contentType":"file"},{"name":"README.fr-FR.md","path":"README.fr-FR.md","contentType":"file"},{"name":"README.ja-JP.md","path":"README.ja-JP.md","contentType":"file"},{"name":"README.ko-KR.md","path":"README.ko-KR.md","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"},{"name":"README.pl-PL.md","path":"README.pl-PL.md","contentType":"file"},{"name":"README.pt-BR.md","path":"README.pt-BR.md","contentType":"file"},{"name":"README.zh-CN.md","path":"README.zh-CN.md","contentType":"file"},{"name":"README.zh-TW.md","path":"README.zh-TW.md","contentType":"file"},{"name":"jest.config.js","path":"jest.config.js","contentType":"file"},{"name":"package-lock.json","path":"package-lock.json","contentType":"file"},{"name":"package.json","path":"package.json","contentType":"file"}],"totalCount":22}},"fileTreeProcessingTime":32.447798999999996,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/zlanusic/javascript-algorithms/branches":{"post":"dQtOoNTK2CgtFzOhqnQ2F2XpxZHmyEncCnRF0EeBVGd1lP6TqpJQiavYv1nxMKQAlSA5yoJJEGeceBeyyQGdhA"},"/zlanusic/javascript-algorithms/branches/fetch_and_merge/master":{"post":"BQ2Zv6xYThy5Jdo-3qmusMHFBchh8goxfEU-RFYA7Nhrm4wWyiS2KZBq65Wcbf8LrQ0En8Jx_NhdItAomMpR6A"},"/zlanusic/javascript-algorithms/branches/fetch_and_merge/master?discard_changes=true":{"post":"c5hCAq_loZPXG2AYWKAacjaVbVMzl7VNLomrqscFa-YdDleryZlZpv5UUbMaZEvJWl1sBJAUQ6QP7kXGCc_W1g"}}},"title":"javascript-algorithms/src/algorithms/graph/bellman-ford at master · zlanusic/javascript-algorithms","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-b84e9496fc59.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
You can’t perform that action at this time.