Find Shortest Paths

Analysis

Find the shortest path between two nodes.

View live example →

With many networks it is useful to know the shortest path between two points (nodes).

The demo shows how to use KeyLines' shortestPaths function to find the path between two points. The network represents cities and the connections between them, with both the travel time and distance between them.

Clicking two nodes consecutively provides the shortest route based on the selection on the side panel. You can also recalculate the same path with a different criteria by selecting a different weighting option.

Key functions used:

Code

import KeyLines from "keylines";
import { data, colours, styles } from "./data.js";

let chart;
const infoFields = document.getElementsByClassName("info");
let pathEnds = [null, null];
let pathWeighting = document.querySelector('input[name="option"]:checked').value;
let clearAnimation = [];

function formatDuration(number) {
  const minsAsNumber = number % 60;
  const hours = (number - minsAsNumber) / 60;
  const minsAsTwoDigits = minsAsNumber < 10 ? `0${minsAsNumber}` : minsAsNumber;
  return `${hours}:${minsAsTwoDigits}`;
}

// update the sidebar to show info about the path
function updateSideInfo(pathLength, pathDistance) {
  infoFields[0].innerHTML = pathEnds[0];
  infoFields[1].innerHTML = pathEnds[1];
  infoFields[2].innerHTML = "&nbsp;";
  // user clicked a link (undefined) or 2 nodes that have no path between them (-0.5)
  if (pathLength < 0 || pathLength === undefined) {
    if (pathLength < 0) infoFields[2].innerHTML = "No available path";
    infoFields[3].innerHTML = "N/A";
    infoFields[4].innerHTML = "N/A";
  } else if (pathWeighting === "distance") {
    infoFields[3].innerHTML = pathLength;
    infoFields[4].innerHTML = `${pathDistance}km`;
  } else if (pathWeighting === "time") {
    infoFields[3].innerHTML = pathLength;
    infoFields[4].innerHTML = `${formatDuration(pathDistance)}hrs`;
  } else if (pathWeighting === "equal") {
    infoFields[3].innerHTML = pathLength;
    infoFields[4].innerHTML = `${pathDistance} links`;
  } else {
    Array.from(infoFields).forEach((element) => {
      element.innerHTML = "";
    });
  }
}

async function animateShortestPath(path, weighting) {
  for (const [index, item] of path.onePath.entries()) {
    if (index % 2 === 0) {
      // item is a node, so update border & enlargement
      await chart.animateProperties(
        { id: item, b: colours[weighting], ...styles.pathNode },
        { time: 30 }
      );
      clearAnimation.push({ id: item, ...styles.node });
    } else {
      // item is a link, so update colour and width
      await chart.animateProperties(
        {
          id: item,
          c: colours[weighting],
          border: { colour: colours[weighting], width: 2, radius: 3 },
          ...styles.pathLink,
        },
        { time: 30 }
      );
      clearAnimation.push({ id: item, ...styles.link });
    }
  }
}

function selectionChanged(node1, node2) {
  chart.animateProperties(clearAnimation, { time: 30 });
  clearAnimation = [];

  // if we have 2 path ends, calculate the path and animate it
  if (node1 && node2) {
    const options = { direction: "any" };
    if (pathWeighting !== "equal") options.value = pathWeighting;
    const path = chart.graph().shortestPaths(node1, node2, options);

    animateShortestPath(path, pathWeighting);
    updateSideInfo((path.onePath.length - 1) / 2, path.distance);
  }
}

function selectNode({ id }) {
  function resetSelection() {
    chart.selection({});
    pathEnds = [null, null];
    selectionChanged();
    updateSideInfo();
  }
  const validatedItem = chart.getItem(id);

  if (validatedItem && validatedItem.type === "node") {
    // if user clicked a node, store it as a path end
    pathEnds = [pathEnds[1], null];
    pathEnds[1] = id;

    // if we have 2 ends, give them to the selection change handler
    if (pathEnds[0] !== null) selectionChanged(pathEnds[0], pathEnds[1]);
  } else if (id === null || validatedItem) {
    // user clicked the background or a link
    resetSelection();
  }
}

function initialiseInteractions() {
  chart.on("click", selectNode);
  // prevent users selecting more than one node
  chart.on("selection-change", () => {
    if (chart.selection()[1]) chart.selection([]);
  });

  const radioButtons = document.querySelectorAll('input[name="option"]');
  Array.from(radioButtons).forEach((button) => {
    button.addEventListener("click", () => {
      pathWeighting = button.value;
      selectionChanged(pathEnds[0], pathEnds[1]);
    });
  });
}

async function startKeyLines() {
  const chartOptions = {
    logo: { u: "/images/Logo.png" },
    linkStyle: { inline: true },
    drag: { links: false },
    handMode: true,
    overview: false,
    minZoom: 0.45,
    selectedLink: {
      border: {
        radius: 3,
        colour: colours.themeDark,
        width: 1,
      },
      fbc: colours.themeBase,
      fc: "white",
      c: colours.themeDark,
    },
    selectedNode: {
      bw: 4,
      fc: "white",
    },
    zoom: {
      adaptiveStyling: false,
    },
  };

  chart = await KeyLines.create({
    container: "klchart",
    options: chartOptions,
  });

  chart.load(data());
  chart.zoom("fit", { animate: false });
  initialiseInteractions();
}

window.addEventListener("DOMContentLoaded", startKeyLines);

Data

const items = [
  {
    type: "link",
    id1: "Atlantic City",
    id2: "Baltimore",
    d: {
      distance: 152,
      time: 158,
    },
    id: "link21",
    t: "2:38 hrs\n152 miles",
  },
  {
    type: "link",
    id1: "Atlantic City",
    id2: "Norfolk",
    d: {
      distance: 322,
      time: 466,
    },
    id: "link22",
    t: "7:46 hrs\n322 miles",
  },
  {
    type: "link",
    id1: "Atlantic City",
    id2: "Philadelphia",
    d: {
      distance: 62,
      time: 64,
    },
    id: "link23",
    t: "1:04 hrs\n62 miles",
  },
  {
    type: "link",
    id1: "Buffalo",
    id2: "Harrisburg",
    d: {
      distance: 289,
      time: 340,
    },
    id: "link24",
    t: "5:40 hrs\n289 miles",
  },
  {
    type: "link",
    id1: "Buffalo",
    id2: "Scranton",
    d: {
      distance: 287,
      time: 296,
    },
    id: "link25",
    t: "4:56 hrs\n287 miles",
  },
  {
    type: "link",
    id1: "Charleston",
    id2: "Pittsburgh",
    d: {
      distance: 229,
      time: 229,
    },
    id: "link26",
    t: "3:49 hrs\n229 miles",
  },
  {
    type: "link",
    id1: "Charleston",
    id2: "Richmond",
    d: {
      distance: 316,
      time: 316,
    },
    id: "link27",
    t: "5:16 hrs\n316 miles",
  },
  {
    type: "link",
    id1: "Charleston",
    id2: "Washington",
    d: {
      distance: 366,
      time: 366,
    },
    id: "link28",
    t: "6:06 hrs\n366 miles",
  },
  {
    type: "link",
    id1: "Cincinnati",
    id2: "Columbus",
    d: {
      distance: 111,
      time: 115,
    },
    id: "link29",
    t: "1:55 hrs\n111 miles",
  },
  {
    type: "link",
    id1: "Cleveland",
    id2: "Charleston",
    d: {
      distance: 250,
      time: 256,
    },
    id: "link30",
    t: "4:16 hrs\n250 miles",
  },
  {
    type: "link",
    id1: "Cleveland",
    id2: "Youngstown",
    d: {
      distance: 76,
      time: 80,
    },
    id: "link31",
    t: "1:20 hrs\n76 miles",
  },
  {
    type: "link",
    id1: "Columbus",
    id2: "Charleston",
    d: {
      distance: 167,
      time: 207,
    },
    id: "link32",
    t: "3:27 hrs\n167 miles",
  },
  {
    type: "link",
    id1: "Columbus",
    id2: "Cleveland",
    d: {
      distance: 142,
      time: 147,
    },
    id: "link33",
    t: "2:27 hrs\n142 miles",
  },
  {
    type: "link",
    id1: "Columbus",
    id2: "Washington",
    d: {
      distance: 417,
      time: 428,
    },
    id: "link34",
    t: "7:08 hrs\n417 miles",
  },
  {
    type: "link",
    id1: "Detroit",
    id2: "Toledo",
    d: {
      distance: 62,
      time: 66,
    },
    id: "link35",
    t: "1:06 hrs\n62 miles",
  },
  {
    type: "link",
    id1: "Harrisburg",
    id2: "Baltimore",
    d: {
      distance: 88,
      time: 92,
    },
    id: "link36",
    t: "1:32 hrs\n88 miles",
  },
  {
    type: "link",
    id1: "Harrisburg",
    id2: "Philadelphia",
    d: {
      distance: 114,
      time: 118,
    },
    id: "link37",
    t: "1:58 hrs\n114 miles",
  },
  {
    type: "link",
    id1: "Harrisburg",
    id2: "Scranton",
    d: {
      distance: 120,
      time: 123,
    },
    id: "link38",
    t: "2:03 hrs\n120 miles",
  },
  {
    type: "link",
    id1: "Harrisburg",
    id2: "Washington",
    d: {
      distance: 126,
      time: 138,
    },
    id: "link39",
    t: "2:18 hrs\n126 miles",
  },
  {
    type: "link",
    id1: "London",
    id2: "Buffalo",
    d: {
      distance: 157,
      time: 180,
    },
    id: "link40",
    t: "3:00 hrs\n157 miles",
  },
  {
    type: "link",
    id1: "London",
    id2: "Detroit",
    d: {
      distance: 127,
      time: 127,
    },
    id: "link41",
    t: "2:07 hrs\n127 miles",
  },
  {
    type: "link",
    id1: "London",
    id2: "Toronto",
    d: {
      distance: 125,
      time: 125,
    },
    id: "link42",
    t: "2:05 hrs\n125 miles",
  },
  {
    type: "link",
    id1: "New York",
    id2: "Atlantic City",
    d: {
      distance: 134,
      time: 151,
    },
    id: "link43",
    t: "2:31 hrs\n134 miles",
  },
  {
    type: "link",
    id1: "New York",
    id2: "Harrisburg",
    d: {
      distance: 178,
      time: 198,
    },
    id: "link44",
    t: "3:18 hrs\n178 miles",
  },
  {
    type: "link",
    id1: "New York",
    id2: "Philadelphia",
    d: {
      distance: 99,
      time: 120,
    },
    id: "link45",
    t: "2:00 hrs\n99 miles",
  },
  {
    type: "link",
    id1: "New York",
    id2: "Scranton",
    d: {
      distance: 131,
      time: 146,
    },
    id: "link46",
    t: "2:26 hrs\n131 miles",
  },
  {
    type: "link",
    id1: "New York",
    id2: "Youngstown",
    d: {
      distance: 410,
      time: 467,
    },
    id: "link47",
    t: "7:47 hrs\n410 miles",
  },
  {
    type: "link",
    id1: "Philadelphia",
    id2: "Baltimore",
    d: {
      distance: 102,
      time: 102,
    },
    id: "link48",
    t: "1:42 hrs\n102 miles",
  },
  {
    type: "link",
    id1: "Philadelphia",
    id2: "Norfolk",
    d: {
      distance: 276,
      time: 348,
    },
    id: "link49",
    t: "5:48 hrs\n276 miles",
  },
  {
    type: "link",
    id1: "Pittsburgh",
    id2: "Buffalo",
    d: {
      distance: 216,
      time: 219,
    },
    id: "link50",
    t: "3:39 hrs\n216 miles",
  },
  {
    type: "link",
    id1: "Pittsburgh",
    id2: "Harrisburg",
    d: {
      distance: 204,
      time: 208,
    },
    id: "link51",
    t: "3:28 hrs\n204 miles",
  },
  {
    type: "link",
    id1: "Pittsburgh",
    id2: "Washington",
    d: {
      distance: 252,
      time: 242,
    },
    id: "link52",
    t: "4:02 hrs\n252 miles",
  },
  {
    type: "link",
    id1: "Richmond",
    id2: "Norfolk",
    d: {
      distance: 93,
      time: 97,
    },
    id: "link53",
    t: "1:37 hrs\n93 miles",
  },
  {
    type: "link",
    id1: "Richmond",
    id2: "Washington",
    d: {
      distance: 106,
      time: 110,
    },
    id: "link54",
    t: "1:50 hrs\n106 miles",
  },
  {
    type: "link",
    id1: "Scranton",
    id2: "Philadelphia",
    d: {
      distance: 126,
      time: 131,
    },
    id: "link55",
    t: "2:11 hrs\n126 miles",
  },
  {
    type: "link",
    id1: "Toledo",
    id2: "Cincinnati",
    d: {
      distance: 198,
      time: 203,
    },
    id: "link56",
    t: "3:23 hrs\n198 miles",
  },
  {
    type: "link",
    id1: "Toledo",
    id2: "Cleveland",
    d: {
      distance: 115,
      time: 115,
    },
    id: "link57",
    t: "1:55 hrs\n115 miles",
  },
  {
    type: "link",
    id1: "Toledo",
    id2: "Columbus",
    d: {
      distance: 142,
      time: 164,
    },
    id: "link58",
    t: "2:44 hrs\n142 miles",
  },
  {
    type: "link",
    id1: "Toronto",
    id2: "Buffalo",
    d: {
      distance: 107,
      time: 107,
    },
    id: "link59",
    t: "1:47 hrs\n107 miles",
  },
  {
    type: "link",
    id1: "Youngstown",
    id2: "Harrisburg",
    d: {
      distance: 267,
      time: 272,
    },
    id: "link60",
    t: "4:32 hrs\n267 miles",
  },
  {
    type: "link",
    id1: "Youngstown",
    id2: "Pittsburgh",
    d: {
      distance: 70,
      time: 73,
    },
    id: "link61",
    t: "1:13 hrs\n70 miles",
  },
  {
    type: "node",
    id: "Atlantic City",
    x: 2045,
    y: 779,
    t: "Atlantic City",
  },
  {
    type: "node",
    id: "Baltimore",
    x: 1836,
    y: 848,
    t: "Baltimore",
  },
  {
    type: "node",
    id: "Buffalo",
    x: 1322,
    y: 473,
    t: "Buffalo",
  },
  {
    type: "node",
    id: "Charleston",
    x: 1235,
    y: 1211,
    t: "Charleston",
  },
  {
    type: "node",
    id: "Cincinnati",
    x: 804,
    y: 1241,
    t: "Cincinnati",
  },
  {
    type: "node",
    id: "Cleveland",
    x: 1067,
    y: 779,
    t: "Cleveland",
  },
  {
    type: "node",
    id: "Columbus",
    x: 972,
    y: 1062,
    t: "Columbus",
  },
  {
    type: "node",
    id: "Detroit",
    x: 828,
    y: 702,
    t: "Detroit",
  },
  {
    type: "node",
    id: "Harrisburg",
    x: 1703,
    y: 738,
    t: "Harrisburg",
  },
  {
    type: "node",
    id: "London",
    x: 1040,
    y: 527,
    t: "London",
  },
  {
    type: "node",
    id: "New York",
    x: 2027,
    y: 537,
    t: "New York",
  },
  {
    type: "node",
    id: "Norfolk",
    x: 2031,
    y: 1221,
    t: "Norfolk",
  },
  {
    type: "node",
    id: "Philadelphia",
    x: 1910,
    y: 716,
    t: "Philadelphia",
  },
  {
    type: "node",
    id: "Pittsburgh",
    x: 1323,
    y: 855,
    t: "Pittsburgh",
  },
  {
    type: "node",
    id: "Richmond",
    x: 1817,
    y: 1178,
    t: "Richmond",
  },
  {
    type: "node",
    id: "Scranton",
    x: 1770,
    y: 525,
    t: "Scranton",
  },
  {
    type: "node",
    id: "Toledo",
    x: 830,
    y: 816,
    t: "Toledo",
  },
  {
    type: "node",
    id: "Toronto",
    x: 1208,
    y: 392,
    t: "Toronto",
  },
  {
    type: "node",
    id: "Washington",
    x: 1772,
    y: 956,
    t: "Washington",
  },
  {
    type: "node",
    id: "Youngstown",
    x: 1215,
    y: 809,
    t: "Youngstown",
  },
];

export const colours = {
  time: "rgb(255,153,0)",
  distance: "rgb(64,77,254)",
  equal: "rgb(220,0,0)",
  themeBase: "#CBA2BC",
  themeDark: "#6F0046",
  linkDefault: "#808080",
};

export const styles = {
  node: {
    c: colours.themeBase,
    b: colours.themeDark,
    bw: 2,
    e: 1,
    fb: true,
    fc: "black",
    sh: "box", // allows the label to grow wider and hence larger than if 'circle'
    fbc: "rgba(255,255,255,0)",
    borderRadius: 30,
  },
  pathNode: {
    e: 1.2,
    bw: 4,
    fc: "white",
  },
  nodeLabel: {
    fs: "auto",
    maxHeight: 16,
  },
  link: {
    c: colours.linkDefault,
    w: 1,
    fbc: "white",
    fc: "black",
    fs: 10,
    border: { radius: 3 },
    priority: 0,
  },
  pathLink: {
    w: 5,
    fbc: colours.themeBase,
    fc: "white",
    priority: 1,
  },
};

export function data() {
  return {
    type: "LinkChart",
    items: items.map((item) => {
      return item.type === "node"
        ? { ...item, ...styles.node, t: { t: item.t, ...styles.nodeLabel } }
        : { ...item, ...styles.link };
    }),
  };
}

HTML

<!doctype html>
<html lang="en" style="background-color: #2d383f">
  <head>
    <meta charset="utf-8" />
    <title>Find Shortest Paths</title>
    <link rel="stylesheet" type="text/css" href="@ci/theme/kl/css/keylines.css" />
    <link rel="stylesheet" type="text/css" href="@ci/theme/kl/css/minimalsdk.css" />
    <link rel="stylesheet" type="text/css" href="@ci/theme/kl/css/sdk-layout.css" />
    <link rel="stylesheet" type="text/css" href="@ci/theme/kl/css/demo.css" />
  </head>
  <body>
    <div id="klchart" class="klchart"></div>
    <script type="module" src="./code.js"></script>
  </body>
</html>

Search

Find Shortest Paths

Terms of use