Skip to content

Instantly share code, notes, and snippets.

@sdjacobs

sdjacobs/cities.tsv

Last active March 2, 2019 02:14
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sdjacobs/3900867adc06c7680d48 to your computer and use it in GitHub Desktop.
Save sdjacobs/3900867adc06c7680d48 to your computer and use it in GitHub Desktop.
Download ZIP
Dijkstra's algorithm in Javascript/D3
Raw
readme.md

This example shows an implementation of Dijkstra's algorithm for finding distances in a graph, implemented as a D3 plugin.

The data for this example came from infoplease.com, and the graph layout was adapted from the D3 force layout example.

Click a city to start Dijkstra's algorithm with that node as the source. You can view city names by hovering over nodes in the graph. When Dijkstra's algorithm completes, hover over a node to see its distance from the source city.

Raw
cities.tsv
Cities1 Birmingham Boston Buffalo Chicago Cleveland Dallas Denver Detroit El Paso Houston Indianapolis Kansas City Los Angeles Louisville Memphis Miami Minneapolis New Orleans New York Omaha Philadelphia Phoenix Pittsburgh St. Louis Salt Lake City San Francisco Seattle Washington
Birmingham, Ala. — 1194 947 657 734 653 1318 754 1278 692 492 703 2078 378 249 777 1067 347 983 907 894 1680 792 508 1805 2385 2612 751
Boston, Mass. 1194 — 457 983 639 1815 1991 702 2358 1886 940 1427 3036 996 1345 1539 1402 1541 213 1458 304 2664 597 1179 2425 3179 3043 440
Buffalo, N.Y. 947 457 — 536 192 1387 1561 252 1928 1532 510 997 2606 571 965 1445 955 1294 436 1011 383 2234 219 749 1978 2732 2596 386
Chicago, Ill. 657 983 536 — 344 931 1050 279 1439 1092 189 503 2112 305 546 1390 411 947 840 493 758 1729 457 293 1458 2212 2052 695
Cleveland, Ohio 734 639 192 344 — 1205 1369 175 1746 1358 318 815 2424 379 773 1325 763 1102 514 819 432 2052 131 567 1786 2540 2404 369
Dallas, Tex. 653 1815 1387 931 1205 — 801 1167 625 242 877 508 1425 865 470 1332 969 504 1604 661 1515 1027 1237 638 1239 1765 2122 1372
Denver, Colo. 1318 1991 1561 1050 1369 801 — 1310 652 1032 1051 616 1174 1135 1069 2094 867 1305 1780 559 1698 836 1411 871 512 1266 1373 1635
Detroit, Mich. 754 702 252 279 175 1167 1301 — 1696 1312 290 760 2369 378 756 1409 698 1101 671 754 589 1986 288 529 1721 2475 2339 526
El Paso, Tex. 1278 2358 1928 1439 1746 625 652 1696 — 756 1418 936 800 1443 1095 1957 1353 1121 2147 1015 2065 402 1778 1179 877 1202 1760 1997
Houston, Tex. 692 1886 1532 1092 1358 242 1032 1312 756 — 1022 750 1556 981 586 1237 1211 365 1675 903 1586 1158 1395 799 1465 1958 2348 1443
Indianapolis, Ind. 492 940 510 189 318 877 1051 290 1418 1022 — 487 2096 114 466 1225 600 839 729 590 647 1713 360 239 1545 2299 2241 565
Kansas City, Mo. 703 1427 997 503 815 508 616 760 936 750 487 — 1609 519 454 1479 466 839 1216 204 1134 1226 847 255 1128 1882 1909 1071
Los Angeles, Calif. 2078 3036 2606 2112 2424 1425 1174 2369 800 1556 2096 1609 — 2128 1847 2757 2041 1921 2825 1733 2743 398 2456 1864 728 403 1150 2680
Louisville, Ky. 378 996 571 305 379 865 1135 378 1443 981 114 519 2128 — 396 1111 716 725 785 704 703 1749 416 264 1647 2401 2355 601
Memphis, Tenn. 249 1345 965 546 773 470 1069 756 1095 586 466 454 1847 396 — 1025 854 401 1134 658 1045 1464 810 295 1556 2151 2363 902
Miami, Fla. 777 1539 1445 1390 1325 1332 2094 1409 1957 1237 1225 1479 2757 1111 1025 — 1801 892 1328 1683 1239 2359 1250 1241 2571 3097 3389 1101
Minneapolis, Minn. 1067 1402 955 411 763 969 867 698 1353 1211 600 466 2041 716 854 1801 — 1255 1259 373 1177 1644 876 559 1243 1997 1641 1114
New Orleans, La. 347 1541 1294 947 1102 504 1305 1101 1121 365 839 839 1921 725 401 892 1255 — 1330 1043 1241 1523 1118 696 1743 2269 2626 1098
New York, N.Y. 983 213 436 840 514 1604 1780 671 2147 1675 729 1216 2825 785 1134 1328 1259 1330 — 1315 93 2442 386 968 2282 3036 2900 229
Omaha, Nebr. 907 1458 1011 493 819 661 559 754 1015 903 590 204 1733 704 658 1683 373 1043 1315 — 1233 1305 932 459 967 1721 1705 1178
Philadelphia, Pa. 894 304 383 758 432 1515 1698 589 2065 1586 647 1134 2743 703 1045 1239 1177 1241 93 1233 — 2360 304 886 2200 2954 2818 140
Phoenix, Ariz. 1680 2664 2234 1729 2052 1027 836 1986 402 1158 1713 1226 398 1749 1464 2359 1644 1523 2442 1305 2360 — 2073 1485 651 800 1482 2278
Pittsburgh, Pa. 792 597 219 457 131 1237 1411 288 1778 1395 360 847 2456 416 810 1250 876 1118 386 932 304 2073 — 599 1899 2653 2517 241
St. Louis, Mo. 508 1179 749 293 567 638 871 529 1179 799 239 255 1864 264 295 1241 559 696 968 459 886 1485 599 — 1383 2137 2164 836
Salt Lake City, Utah 1805 2425 1978 1458 1786 1239 512 1721 877 1465 1545 1128 728 1647 1556 2571 1243 1743 2282 967 2200 651 1899 1383 — 754 883 2110
San Francisco, Calif. 2385 3179 2732 2212 2540 1765 1266 2475 1202 1958 2299 1882 403 2401 2151 3097 1997 2269 3036 1721 2954 800 2653 2137 754 — 817 2864
Seattle, Wash. 2612 3043 2596 2052 2404 2122 1373 2339 1760 2348 2241 1909 1150 2355 2363 3389 1641 2606 2900 1705 2818 1482 2517 2164 883 817 — 2755
Washington, D.C. 751 440 386 695 369 1372 1635 526 1997 1443 565 1071 2680 601 902 1101 1114 1098 229 1170 140 2278 241 836 2110 2864 2755 —
Raw
dijkstra.js
d3.dijkstra = function () {
var dijkstra = {}, nodes, edges, source, dispatch = d3.dispatch("start", "tick", "step", "end");
dijkstra.run = function (src) {
source = src;
var unvisited = [];
nodes.forEach(function (d) {
if (d != src) {
d.distance = Infinity;
unvisited.push(d);
d.visited = false;
}
});
var current = src;
current.distance = 0;
function tick() {
current.visited = true;
current.links.forEach(function(link) {
var tar = link.target;
if (!tar.visited) {
var dist = current.distance + link.value;
tar.distance = Math.min(dist, tar.distance);
}
});
if (unvisited.length == 0 || current.distance == Infinity) {
dispatch.end()
return true;
}
unvisited.sort(function(a, b) {
return b.distance - a.distance
});
current = unvisited.pop()
dispatch.tick();
return false;
}
d3.timer(tick);
};
dijkstra.nodes = function (_) {
if (!arguments.length)
return nodes;
else {
nodes = _;
return dijkstra;
}
};
dijkstra.edges = function (_) {
if (!arguments.length)
return edges;
else {
edges = _;
return dijkstra;
}
};
dijkstra.source = function(_) {
if (!arguments.length)
return source;
else {
source = _;
return dijkstra;
}
};
dispatch.on("start.code", dijkstra.run);
return d3.rebind(dijkstra, dispatch, "on", "end", "start", "tick");
};
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.node {
stroke: #fff;
stroke-width: 1.5px;
}
.link {
stroke: #999;
stroke-opacity: .6;
}
</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="dijkstra.js"></script>
<script>
var width = 960,
height = 500;
var color = d3.scale.category20();
var force = d3.layout.force()
.charge(-120)
.linkDistance(30)
.size([width, height]);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
d3.tsv("cities.tsv", function(error, data) {
var nodes = [], nodesByName = {}, links = [];
function addNodeByName(fullname) {
var name = fullname.split(',')[0];
if (!nodesByName[name]) {
var node = {"name":name, "links":[]}
nodesByName[name] = node;
nodes.push(node);
return node;
}
else
return nodesByName[name];
}
data.forEach(function(d) {
for (k in d) {
if (d.hasOwnProperty(k) && k != "Cities1" && d[k] < 750) {
links.push({"source": addNodeByName(d["Cities1"]), "target": addNodeByName(k), "value": parseInt(d[k])})
}
}
});
force
.nodes(nodes)
.links(links)
.start();
var link = svg.selectAll(".link")
.data(links)
.enter().append("line")
.attr("class", "link")
.style("stroke-width", 1);
var node = svg.selectAll(".node")
.data(nodes)
.enter().append("circle")
.attr("class", "node")
.attr("r", 5)
.style("fill", "grey")
.call(force.drag);
link.each(function(d) {
d.source.links.push(d);
d.selection = d3.select(this);
});
node.each(function(d) {
d.selection = d3.select(this);
});
node.append("title")
.text(function(d) { return d.name; });
link.append("title")
.text(function(d) { return d.source.name + " → " + d.target.name + "\n" + d.value + " mi" });
force.on("tick", function() {
link.attr("x1", function(d) { return d.source.x; })
.attr("y1", function(d) { return d.source.y; })
.attr("x2", function(d) { return d.target.x; })
.attr("y2", function(d) { return d.target.y; });
node.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
});
node.on("mouseover", function(d) {
d3.select(this)
.attr("r", 10)
d.links.forEach(function(l) {
l.selection
.style("stroke-width", 10)
l.target.selection
.attr("r", 7);
});
});
node.on("mouseout", function(d) {
node.attr("r", 5)
link.style("stroke-width", 1);
});
link.on("mouseover", function() {
d3.select(this)
.style("stroke-width", 10);
});
link.on("mouseout", function() {
d3.select(this)
.style("stroke-width", 1);
});
var dijkstra = d3.dijkstra()
.nodes(nodes)
.edges(links);
var color = d3.scale.linear()
.domain([0, 1000, 2500])
.range(["green", "yellow", "red"]);
dijkstra.on("tick", function() {
node.style("fill", function(d) { return color(d.distance); });
});
dijkstra.on("end", function() {
var name = dijkstra.source().name;
node.select("title")
.text(function(d) { return d.name + "\n(" + d.distance + " miles from " + name + ")" });
});
node.on("click", dijkstra.start);
});
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment