Dijkstra, JavaScript, and d3.js

dijkstra

I recently came across a JavaScript library that helps visualize data by pairing data to the DOM, allowing easy HTML generation based on arrays of data. It is a neat idea, and allows for a lot of easy flexibility, so I wanted to give it a try. (http://www.d3js.org)

At the same time, I’ve been wanting to revisit some of the classic computer science algorithms I learned over 10 years ago. In this case, Dijkstra’s. I remember trying to implement Dijkstra’s algorithm in college and never being quite sure that it worked, so I had been wanting to refresh my memory and give it another go.  Dijkstra’s is a fairly visually-oriented algorithm, so it seemed to be a good fit for exploring d3’s capabilities.

I’m fairly satisfied with the results.  The basics layout is a simple grid of vertices joined by edges or random weight. Click any two to set the algorithm in motion.

A few notes of interest about the process:

  • Dijkstra’s has no direction-optimization; it spreads in all directions all at once. This opens up some interesting questions about how to optimize the algorithm by helping it understand where it is headed. It also means that if you cached the distance values, the next time you needed to find a distance from the same start point, you’d be able to skip a lot of the process.
  • OO in JavaScript is easy and powerful.
  • The scope of variables in JavaScript is an easy place to make mistakes.
  • d3.js is fantastic! It allows you to pair your data directly to any part of the DOM, so updates to the data can be mirrored quickly in the HTML. This gives you a lot of control, and at the same time, a lot of options for displaying your data. In this case, I paired my Vertex objects directly to the SVG root element, so it auto-generates all of the vertex and edge SVG elements for me.

Feel free to take a look at my code, and let me know what you think.