A graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.
Click to select source and destination.
| (function() { | |
| function randomInt(min, max) { | |
| return Math.floor(Math.random() * (max - min + 1)) + min; | |
| } | |
| /** | |
| * Vertex | |
| */ | |
| function Vertex(id, row, col) { | |
| this._id = id; | |
| this._edges = []; | |
| this._row = row; | |
| this._col = col; | |
| this._distance = Infinity; | |
| this._visited = false; | |
| this._path = false; | |
| } | |
| Vertex.prototype.id = function() { | |
| return this._id; | |
| } | |
| Vertex.prototype.edges = function() { | |
| return this._edges; | |
| } | |
| Vertex.prototype.row = function() { | |
| return this._row; | |
| } | |
| Vertex.prototype.col = function() { | |
| return this._col; | |
| } | |
| Vertex.prototype.distance = function(distance) { | |
| if (!arguments.length) return this._distance; | |
| this._distance = distance; | |
| return this; | |
| } | |
| Vertex.prototype.visited = function(visited) { | |
| if (!arguments.length) return this._visited; | |
| this._visited = visited; | |
| return this; | |
| } | |
| Vertex.prototype.previous = function(previous) { | |
| if (!arguments.length) return this._previous; | |
| this._previous = previous; | |
| return this; | |
| } | |
| Vertex.prototype.path = function(path) { | |
| if (!arguments.length) return this._path; | |
| this._path = path; | |
| return this; | |
| } | |
| Vertex.prototype.isConnected = function(vertex) { | |
| return this.edges().filter(function(edge) { | |
| return edge.source().id() == vertex.id() || edge.destination().id() == vertex.id() | |
| }).length > 0; | |
| } | |
| Vertex.prototype.connect = function(vertex) { | |
| if( !this.isConnected( vertex ) ) { | |
| var edge = new Edge(this, vertex ); | |
| this.edges().push(edge); | |
| vertex.edges().push(edge); | |
| return edge; | |
| } | |
| return null; | |
| } | |
| Vertex.prototype.findEdge = function( dest ) { | |
| var toRet = null; | |
| var that = this; | |
| that.edges().forEach(function(e) { | |
| if (toRet == null && (e.destination().id() == dest.id() || e.source().id() == dest.id())) { | |
| toRet = e; | |
| } | |
| }); | |
| return toRet; | |
| } | |
| /** | |
| * Edge | |
| */ | |
| function Edge(source, destination) { | |
| this._id = source.id() + "_" + destination.id(); | |
| this._weight = Math.ceil( Math.random() * 10 ); | |
| this._source = source, | |
| this._destination = destination; | |
| this._path = false; | |
| } | |
| Edge.prototype.id = function() { | |
| return this._id; | |
| } | |
| Edge.prototype.weight = function(weight) { | |
| if (!arguments.length) return this._weight; | |
| this._weight = weight; | |
| return this; | |
| } | |
| Edge.prototype.source = function() { | |
| return this._source; | |
| } | |
| Edge.prototype.destination = function() { | |
| return this._destination; | |
| } | |
| Edge.prototype.opposite = function( vertex ) { | |
| if( this._source != null && this._source.id() == vertex.id() ) return this._destination; | |
| else return this._source; | |
| } | |
| Edge.prototype.path = function(path) { | |
| if (!arguments.length) return this._path; | |
| this._path = path; | |
| return this; | |
| } | |
| /** | |
| * Dijkstra algorithm | |
| */ | |
| function dijkstra() { | |
| this._rows = 10; | |
| this._cols = 15; | |
| this._vertices = []; | |
| this._edges = []; | |
| this._unvisited = []; | |
| this._found = false; | |
| this._interval = 5; | |
| this._from = null; | |
| this._to = null; | |
| this._running = false; | |
| this._onStart = function() { console.log("dijkstra start"); } | |
| this._onStep = function() { console.log("dijkstra step"); } | |
| } | |
| dijkstra.prototype.addVertex = function(vertex) { | |
| if (vertex != null && vertex != undefined) { | |
| this._vertices.push(vertex); | |
| return true; | |
| } | |
| return false; | |
| } | |
| dijkstra.prototype.getVertex = function(id) { | |
| return this._vertices[id]; | |
| } | |
| dijkstra.prototype.addEdge = function(edge) { | |
| if (edge != null && edge != undefined) { | |
| this._edges.push(edge); | |
| return true; | |
| } | |
| return false; | |
| } | |
| dijkstra.prototype.neighbors = function(vertex) { | |
| var that = this; | |
| var neighbors = []; | |
| var neighbor = function(id) { | |
| if ( id < that.vertices().length && id >=0) { | |
| var v = that.getVertex(id); | |
| if ((v.row() == vertex.row() + 1 || v.row() == vertex.row() - 1 || v.row() == vertex.row()) && | |
| (v.col() == vertex.col() + 1 || v.col() == vertex.col() - 1 || v.col() == vertex.col()) ) { | |
| neighbors.push(v); | |
| } | |
| } | |
| } | |
| neighbor(vertex.id() + 1); | |
| neighbor(vertex.id() - 1); | |
| neighbor(vertex.id() + that.rows()); | |
| neighbor(vertex.id() - that.rows()); | |
| return neighbors; | |
| } | |
| dijkstra.prototype.vertices = function(vertices) { | |
| if (!arguments.length) return this._vertices; | |
| this._vertices = vertices; | |
| return this; | |
| } | |
| dijkstra.prototype.found = function(found) { | |
| if (!arguments.length) return this._found; | |
| this._found = found; | |
| return this; | |
| } | |
| dijkstra.prototype.running = function(running) { | |
| if (!arguments.length) return this._running; | |
| this._running = running; | |
| return this; | |
| } | |
| dijkstra.prototype.unvisited = function(unvisited) { | |
| if (!arguments.length) { | |
| this._unvisited.sort( function vertexSort(a, b) { | |
| if( a == null && b == null ) return 0; | |
| if( a == null && b != null ) return 1; | |
| if( b == null && a != null ) return -1; | |
| if( a.distance() > b.distance() ) return -1; | |
| if( a.distance() < b.distance() ) return 1; | |
| else return 0; | |
| } ); | |
| return this._unvisited; | |
| } else { | |
| this._unvisited = unvisited; | |
| } | |
| return this; | |
| } | |
| dijkstra.prototype.edges = function(edges) { | |
| if (!arguments.length) return this._edges; | |
| this._edges = edges; | |
| return this; | |
| } | |
| dijkstra.prototype.rows = function(rows) { | |
| if (!arguments.length) return this._rows; | |
| this._rows = rows; | |
| return this; | |
| } | |
| dijkstra.prototype.cols = function(cols) { | |
| if (!arguments.length) return this._cols; | |
| this._cols = cols; | |
| return this; | |
| } | |
| dijkstra.prototype.from = function(from) { | |
| if (!arguments.length) return this._from; | |
| this._from = from; | |
| if (this._from != null) { | |
| this.reset(); | |
| this._from.distance(0); | |
| this.start(); | |
| } | |
| return this; | |
| } | |
| dijkstra.prototype.to = function(to) { | |
| if (!arguments.length) return this._to; | |
| this._to = to; | |
| if (this._to != null) { | |
| this.step(); | |
| } | |
| return this; | |
| } | |
| dijkstra.prototype.interval = function(interval) { | |
| if (!arguments.length) return this._interval; | |
| this._interval = interval; | |
| return this; | |
| } | |
| dijkstra.prototype.onStart = function(onStart) { | |
| if (!arguments.length) return this._onStart; | |
| this._onStart = onStart; | |
| return this; | |
| } | |
| dijkstra.prototype.onStep = function(onStep) { | |
| if (!arguments.length) return this._onStep; | |
| this._onStep = onStep; | |
| return this; | |
| } | |
| dijkstra.prototype.init = function() { | |
| var that = this; | |
| that.from(null); | |
| that.to(null); | |
| that.vertices([]); | |
| that.edges([]); | |
| that.found(false); | |
| that.running(false); | |
| that.start(); | |
| } | |
| dijkstra.prototype.reset = function() { | |
| var that = this; | |
| that.vertices().forEach(function(v) { | |
| v.distance(Infinity); | |
| v.visited(false); | |
| v.previous(null); | |
| v.path(false); | |
| }); | |
| that.edges().forEach(function(e) { | |
| e.path(false); | |
| }); | |
| } | |
| dijkstra.prototype.start = function() { | |
| var that = this; | |
| if (that.from() == null && that.to() == null) { | |
| // Generate the vertices | |
| for( var col = 0; col < that.cols(); col++ ) { | |
| for( var row = 0; row < that.rows(); row++ ) { | |
| var id = (col*that.rows())+row; | |
| var vertex = new Vertex(id, row, col); | |
| that.addVertex(vertex); | |
| } | |
| } | |
| // Generate the edges | |
| for( var col = 0; col < that.cols(); col++ ) { | |
| for( var row = 0; row < that.rows(); row++ ) { | |
| var id = (col*that.rows())+row; | |
| var vertex = that.getVertex(id); | |
| var neighbors = that.neighbors(vertex); | |
| var maxEdges = randomInt(1, neighbors.length); | |
| for (var i = 0; i < maxEdges; i++) { | |
| if (vertex.edges().length < 4 && i < neighbors.length) { | |
| var edge = vertex.connect(neighbors[i]); | |
| that.addEdge(edge); | |
| } | |
| } | |
| } | |
| } | |
| that.reset(); | |
| } | |
| that.unvisited(that.vertices().concat()); | |
| that.found(false); | |
| that.onStart()(); | |
| } | |
| dijkstra.prototype.step = function() { | |
| var that = this; | |
| var currentVertex = that.unvisited().pop(); | |
| that.running(true); | |
| if( currentVertex == that.to() ) { | |
| that.found(true); | |
| that.to().path(true); | |
| that.from().path(true); | |
| } else { | |
| if( currentVertex != null && currentVertex.distance() < Infinity ) { | |
| currentVertex.edges().forEach(function(edge){ | |
| var distance = currentVertex.distance() + edge.weight(); | |
| var vertex = edge.opposite(currentVertex); | |
| if (distance < vertex.distance()) { | |
| vertex.distance(distance); | |
| vertex.previous(currentVertex); | |
| } | |
| }); | |
| currentVertex.visited(true); | |
| } | |
| } | |
| if( that.found() ) { | |
| if( that.to().distance() != Infinity ) { | |
| var cv = that.to(); | |
| var pathBack = ""; | |
| while( cv != that.from() ) { | |
| cv.path(true); | |
| cv.findEdge(cv.previous()).path(true); | |
| cv = cv.previous(); | |
| } | |
| } else { | |
| console.log( "No path found! Hit the end vertex, but distance=Infinity" ); | |
| } | |
| that.onStep()(); | |
| that.running(false); | |
| } else { | |
| // Check if there are still things to find | |
| if( that.unvisited().length > 0 ) { | |
| // Set a timer to pop and run it again at the next interval | |
| that.onStep()(); | |
| setTimeout( function() { that.step() }, that.interval()); | |
| } else { | |
| console.log( "No path found! Ran out of vertices to check." ); | |
| that.running(false); | |
| } | |
| } | |
| } | |
| if (typeof define === "function" && define.amd) { | |
| define(dijkstra); | |
| } else if (typeof module === "object" && module.exports) { | |
| module.exports = dijkstra; | |
| } else { | |
| this.dijkstra = dijkstra; | |
| } | |
| }()) |
| <html> | |
| <head> | |
| <title>Dijkstra</title> | |
| <script src="http://cdnjs.cloudflare.com/ajax/libs/d3/3.4.11/d3.min.js" charset="utf-8"></script> | |
| <script src="./dijkstra.js"></script> | |
| <style> | |
| .vertex circle { | |
| stroke: #bdbdbd; | |
| fill: white; | |
| stroke-width: 2; | |
| } | |
| .vertex.visited circle { | |
| fill: #fdbb84; | |
| } | |
| .vertex.from circle{ | |
| stroke: green; | |
| stroke-width: 2; | |
| } | |
| .vertex.to circle { | |
| stroke: blue; | |
| stroke-width: 2; | |
| } | |
| .vertex.path circle { | |
| stroke: #2ca25f; | |
| fill: #2ca25f; | |
| } | |
| .vertex.from.path circle { | |
| fill: green; | |
| stroke: #2ca25f; | |
| stroke-width: 4; | |
| } | |
| .vertex.to.path circle { | |
| stroke: #2ca25f; | |
| stroke-width: 4; | |
| } | |
| .edge line { | |
| stroke: #bdbdbd; | |
| stroke-width: 3; | |
| } | |
| .edge.path line { | |
| stroke: #2ca25f; | |
| stroke-width: 7; | |
| } | |
| text.weight { | |
| font-size: 10px; | |
| font-weight: bold; | |
| } | |
| text.distance { | |
| font-size: 10px; | |
| font-weight: bold; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| Rows:<input id="rows" type="number" min="3", max="15" width="40" value="15"/> | |
| Columns:<input id="cols" type="number" min="3", max="25" width="40" value="20"/> | |
| <div id="chart"></div> | |
| <script> | |
| var dijkstra = new dijkstra().interval(1).rows(12).cols(20); | |
| var svg = d3.select("#chart").append("svg") | |
| .attr("width", 960) | |
| .attr("height", 450); | |
| var repaint = function() { | |
| var xscale = d3.scale.linear() | |
| .domain([0, dijkstra.cols() * 30]) | |
| .range([0, svg.attr("width")]); | |
| var yscale = d3.scale.linear() | |
| .domain([0, dijkstra.rows() * 30]) | |
| .range([0, svg.attr("height")]); | |
| var radius = (svg.attr("width") > svg.attr("height")) ? yscale(7) : xscale(7); | |
| // Edges | |
| var edge = svg.selectAll(".edge").data(dijkstra.edges(), function(e) { return e.id(); }); | |
| edge.enter() | |
| .append("g") | |
| .classed("edge", true) | |
| .attr("transform", function(d) { return "translate(" + xscale( (0.5 + d.source().col()) * 30) + "," + yscale( (0.5 + d.source().row()) * 30) + ")" } ) | |
| .each(function(d) { | |
| d3.select(this).append("line") | |
| .attr("id", function(d) { return d.id() }) | |
| .attr( "x1", function(d) { return 0 }) | |
| .attr( "y1", function(d) { return 0 }) | |
| .attr( "x2", function(d) { return xscale((d.destination().col() - d.source().col() ) * 30); }) | |
| .attr( "y2", function(d) { return yscale((d.destination().row() - d.source().row() ) * 30); }) | |
| .classed("path", function(d) { return d.path(); }); | |
| d3.select(this).append("text") | |
| .attr("text-anchor", "middle") | |
| .attr("dominant-baseline", "central") | |
| .attr("x", function(d) { return xscale( (d.destination().col() - d.source().col()) / 2 * 30 ) } ) | |
| .attr("y", function(d) { return yscale( (d.destination().row() - d.source().row()) / 2 * 30 ) }) | |
| .text(function(d) { return d.weight(); }) | |
| .classed("distance", true); | |
| }); | |
| edge.each(function(d) { | |
| d3.select(this) | |
| .classed("path", function(d) { return d.path(); }) | |
| }) | |
| // Vertices | |
| var vertex = svg.selectAll(".vertex").data(dijkstra.vertices(), function(v) { return v.id(); }); | |
| vertex.enter() | |
| .append("g") | |
| .classed("vertex", true) | |
| .attr("transform", function(d) { return "translate(" + xscale( (0.5 + d.col()) * 30) + "," + yscale( (0.5 + d.row()) * 30) + ")" } ) | |
| .each(function(d) { | |
| d3.select(this).append("circle") | |
| .attr("id", function(d) { return d.id() }) | |
| .attr("r", function(d) { return radius; }) | |
| .classed("from", function(d) { return dijkstra.from() != null && d.id() == dijkstra.from().id(); }) | |
| .classed("to", function(d) { return dijkstra.to() != null && d.id() == dijkstra.to().id(); }) | |
| .classed("visited", function(d) { return d.visited(); }) | |
| .classed("path", function(d) { return d.path(); }); | |
| d3.select(this).append("text") | |
| .attr("text-anchor", "middle") | |
| .attr("dominant-baseline", "central") | |
| .text(function(d) { return d.distance() != Infinity ? d.distance() : ""; }) | |
| .classed("weight", true); | |
| }).on("click", function() { | |
| if (!dijkstra.running()) { | |
| var v = d3.select(this).data()[0]; | |
| if (dijkstra.from() == null) { | |
| dijkstra.from(v); | |
| } else { | |
| if (dijkstra.to() == null) { | |
| dijkstra.to(v); | |
| } else { | |
| dijkstra.to(null); | |
| dijkstra.from(v); | |
| } | |
| } | |
| } | |
| }); | |
| vertex.each(function(d) { | |
| d3.select(this) | |
| .classed("from", function(d) { return dijkstra.from() != null && d.id() == dijkstra.from().id(); }) | |
| .classed("to", function(d) { return dijkstra.to() != null && d.id() == dijkstra.to().id(); }) | |
| .classed("visited", function(d) { return d.visited(); }) | |
| .classed("path", function(d) { return d.path(); }) | |
| d3.select(this).select("text") | |
| .text(function(d) { return d.distance() != Infinity ? d.distance() : ""; }) | |
| }) | |
| } | |
| dijkstra.onStart(repaint).onStep(repaint).start(); | |
| d3.select("#rows").on("change",function() { | |
| d3.selectAll(".vertex").remove(); | |
| d3.selectAll(".edge").remove(); | |
| dijkstra.rows(+this.value).init(); | |
| }); | |
| d3.select("#cols").on("change",function() { | |
| d3.selectAll(".vertex").remove(); | |
| d3.selectAll(".edge").remove(); | |
| dijkstra.cols(+this.value).init(); | |
| }); | |
| </script> | |
| </body> | |
| </html> |