|
| 1 | +<!DOCTYPE html> |
| 2 | +<html lang="en"> |
| 3 | +<head> |
| 4 | + <meta charset="utf-8"> |
| 5 | + <title>JSDoc: Source: graphs/shortest-path/bellman-ford.js</title> |
| 6 | + |
| 7 | + <script src="scripts/prettify/prettify.js"> </script> |
| 8 | + <script src="scripts/prettify/lang-css.js"> </script> |
| 9 | + <!--[if lt IE 9]> |
| 10 | + <script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script> |
| 11 | + <![endif]--> |
| 12 | + <link type="text/css" rel="stylesheet" href="styles/prettify-tomorrow.css"> |
| 13 | + <link type="text/css" rel="stylesheet" href="styles/jsdoc-default.css"> |
| 14 | +</head> |
| 15 | + |
| 16 | +<body> |
| 17 | + |
| 18 | +<div id="main"> |
| 19 | + |
| 20 | + <h1 class="page-title">Source: graphs/shortest-path/bellman-ford.js</h1> |
| 21 | + |
| 22 | + |
| 23 | + |
| 24 | + |
| 25 | + |
| 26 | + <section> |
| 27 | + <article> |
| 28 | + <pre class="prettyprint source linenums"><code>(function (global) { |
| 29 | + 'use strict'; |
| 30 | + |
| 31 | + function Edge(u, v, weight) { |
| 32 | + this.from = u; |
| 33 | + this.to = v; |
| 34 | + this.weight = weight; |
| 35 | + } |
| 36 | + |
| 37 | + /** |
| 38 | + * Bellman–Ford algorithm computes shortest paths from a single source |
| 39 | + * vertex to all of the other vertices in a weighted digraph (negative weights allowed).<br><br> |
| 40 | + * Time complexity: O(|V||E|) where V and E are the number of vertices and edges respectively. |
| 41 | + * |
| 42 | + * @public |
| 43 | + * @module graphs/shortest-path/bellman-ford |
| 44 | + * @param {Array} vertexes Vertices of the graph. |
| 45 | + * @param {Array} edges Edges of the graph. |
| 46 | + * @param {Number} source Start vertex. |
| 47 | + * @returns {Object} Object with two arrays (parents and distances) with shortest-path information. |
| 48 | + * |
| 49 | + * @example |
| 50 | + * require('path-to-algorithms/src/graphs/shortest-path/bellman-ford'); |
| 51 | + * |
| 52 | + * var glob = (typeof window === 'undefined') ? global : window; |
| 53 | + * var Edge = glob.Edge; |
| 54 | + * var bellmanFord = glob.bellmanFord; |
| 55 | + * var edges = []; |
| 56 | + * var vertexes = [0, 1, 2, 3, 4]; |
| 57 | + * |
| 58 | + * edges.push(new Edge(0, 1, -1)); |
| 59 | + * edges.push(new Edge(0, 2, 4)); |
| 60 | + * edges.push(new Edge(1, 2, 3)); |
| 61 | + * edges.push(new Edge(1, 3, 2)); |
| 62 | + * edges.push(new Edge(3, 1, 1)); |
| 63 | + * edges.push(new Edge(4, 3, -3)); |
| 64 | + * edges.push(new Edge(1, 4, 2)); |
| 65 | + * edges.push(new Edge(3, 2, 5)); |
| 66 | + * |
| 67 | + * // { |
| 68 | + * // parents: { '0': null, '1': 0, '2': 1, '3': 4, '4': 1 }, |
| 69 | + * // distances: { '0': 0, '1': -1, '2': 2, '3': -2, '4': 1 } |
| 70 | + * // } |
| 71 | + * var pathInfo = bellmanFord(vertexes, edges, 0); |
| 72 | + */ |
| 73 | + function bellmanFord(vertexes, edges, source) { |
| 74 | + var distances = {}, parents = {}, c; |
| 75 | + for (var i = 0; i < vertexes.length; i += 1) { |
| 76 | + distances[vertexes[i]] = Infinity; |
| 77 | + parents[vertexes[i]] = null; |
| 78 | + } |
| 79 | + distances[source] = 0; |
| 80 | + for (i = 0; i < vertexes.length - 1; i += 1) { |
| 81 | + for (var j = 0; j < edges.length; j += 1) { |
| 82 | + c = edges[j]; |
| 83 | + if (distances[c.from] + c.weight < distances[c.to]) { |
| 84 | + distances[c.to] = distances[c.from] + c.weight; |
| 85 | + parents[c.to] = c.from; |
| 86 | + } |
| 87 | + } |
| 88 | + } |
| 89 | + |
| 90 | + for (i = 0; i < edges.length; i += 1) { |
| 91 | + c = edges[i]; |
| 92 | + if (distances[c.from] + c.weight < distances[c.to]) { |
| 93 | + return undefined; |
| 94 | + } |
| 95 | + } |
| 96 | + |
| 97 | + return { parents: parents, distances: distances }; |
| 98 | + } |
| 99 | + |
| 100 | + global.Edge = Edge; |
| 101 | + global.bellmanFord = bellmanFord; |
| 102 | + |
| 103 | +}((typeof window === 'undefined') ? global : window));</code></pre> |
| 104 | + </article> |
| 105 | + </section> |
| 106 | + |
| 107 | + |
| 108 | + |
| 109 | + |
| 110 | +</div> |
| 111 | + |
| 112 | +<nav> |
| 113 | + <h2><a href="index.html">Index</a></h2><h3>Modules</h3><ul><li><a href="topological-sort.html">graphs/others/topological-sort</a></li><li><a href="bfs.html">graphs/searching/bfs</a></li><li><a href="dfs.html">graphs/searching/dfs</a></li><li><a href="bellman-ford.html">graphs/shortest-path/bellman-ford</a></li><li><a href="dijkstra.html">graphs/shortest-path/dijkstra</a></li><li><a href="floyd-warshall.html">graphs/shortest-path/floyd-warshall</a></li></ul><h3>Classes</h3><ul><li><a href="Edge.html">Edge</a></li><li><a href="Graph.html">Graph</a></li><li><a href="Vertex.html">Vertex</a></li></ul> |
| 114 | +</nav> |
| 115 | + |
| 116 | +<br clear="both"> |
| 117 | + |
| 118 | +<footer> |
| 119 | + Documentation generated by <a href="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha5</a> on Fri Jan 09 2015 21:22:24 GMT+0200 (EET) |
| 120 | +</footer> |
| 121 | + |
| 122 | +<script> prettyPrint(); </script> |
| 123 | +<script src="scripts/linenumber.js"> </script> |
| 124 | +</body> |
| 125 | +</html> |
0 commit comments