3
\$\begingroup\$

Problem:
I have a weighted graph. I want to get distance from definite point to all other points in the graph.(and then get path to them)
I used modified dijkstra algorithm

So, here is code:

var get_path = function(graph, a) {
// declaration
let cache, i, v, queue, node, links, root,
    j, link, c, n, d, max, w, L = graph.length;

// initialization
cache = Array(L);
i = L;
while (--i >= 0) {
    v = graph[i];
    cache[v.id] = {
        id: v.id,
        distance: Infinity,
        links: v.links,
        prev: null,
    };
}
root = cache[a];
root.distance = 0;
queue = [root];

// processing
i = 0;
while (i < queue.length) {
    node = queue[i];
    links = node.links;
    j = links.length;
    while (--j >= 0) {
        link = links[j];
        c = cache[link.id];
        d = node.distance + link.weight;
        if (d < c.distance) {
            c.prev = node;
            c.distance = d;
            queue.push(c);
        }
    }
    i++;
}

return cache;
}

Graph format is:

graph = [
  {
    id: 1,
    links: [
      {
        id: 2,
        weight: 1,
      },
      {
        id: 3,
        weight: 1,
      },
    ],
  },
  {
    id: 2,
    links: [
      {
        id: 1,
        weight: 1,
      },
      {
        id: 4,
        weight: 2,
      }
    ]
  },
  {
    id: 3,
    links: [
      {
        id: 1,
        weight: 1,
      },
      {
        id: 4,
        weight: 3,
      }
    ]
  },
  {
    id: 4,
    links: [
      {
        id: 2,
        weight: 2,
      },
      {
        id: 1,
        weight: 1,
      },
      {
        id: 3,
        weight: 3,
      },
      {
        id: 5,
        weight: 1,
      }
    ]
  }, 
  {
    id: 5,
    links: [
      {
        id: 4,
        weight: 1,
      }
    ]
  }
]

Performance:
In my PC this algorithm works with graph of ~160 vertices and ~350 edges about 0.03-0.06ms. But I need faster!

You can measure performance on your PC here

Question: How to make this code (function get_path()) faster? Is it possible on JavaScript? If I should change the format of graph to make algorithm faster it's not a problem.


Or I exhausted possibilities of JavaScript?

Improve this question
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Your code is optimal as a general purpose solution so for further optimization you will need to target known structural regularities. EG if the set of nodes A must pass through C to get to nodes not in A. You can then cache all shortest paths from C to any node in A. Any path from B (B is not in set A) to B1 (B1 is in set A) need only find shortest path to C, the path from C to B1 will be cached by index of B1. Without knowing what the graph represents or how and how often it is constructed there is no way of knowing if such optimizations will pay off \$\endgroup\$
    – Blindman67
    Feb 5, 2021 at 15:09

1 Answer 1

Reset to default
1
\$\begingroup\$

Interesting question;

Naming

  • The names are on the whole terrible, it really blocks the reading flow, the only good 1 letter variable is i
  • Further evidence of the bad naming is that I only realized that n, w, and max are never used because of jshint.com
  • JavaScript follows lowerCamelCase so get_path -> getPath
  • In fact, even getPath would be a bad name, because you are not getting a path, getPaths could be better (you are getting more than 1 ), but getDistances or even getDistancesFromNode seems best

Declarations

  • You are mixing var and let in your code, I would stick to let and const

  • You are not declaring res at all (now it's a global) because this

    var s_t = performance.now()
res = get_path(graph, 157)

    should be

    var s_t = performance.now(),
res = get_path(graph, 157)

Performance

This is already quite impressive, the only thing I noticed is that you process child nodes even if their child count is one (meaning really zero, since that 1 node must be the parent).

I assume the while loops are meant to be the fastest approach, however it seems that the fastest approach is now the most readable approach.

If you were allowed to just use/modify graph instead of cache it would be faster, of course the code reviewer would have told you that's not clean ;)

Comments

Comments should be meaningful, these comments are rather obvious.

All in all, if I had to maintain this, then I would rewrite with proper variable names but otherwise this is perfectly maintainable.

function getDistancesFromNode(graph, origin) {

  let cache, i, j, queue, node, links, root,
      link, nextNode, distance, nodeCount = graph.length;

  cache = Array(nodeCount);
  i = nodeCount;
  while (--i >= 0) {
      node = graph[i];
      cache[node.id] = {
          id: node.id,
          distance: Infinity,
          links: node.links,
          prev: null,
      };
  }
  root = cache[origin];
  root.distance = 0;
  queue = [root];

  i = 0;
  while (i < queue.length) {
      node = queue[i];
      links = node.links;
      j = links.length;
      while (--j >= 0) {
          link = links[j];
          nextNode = cache[link.id];
          distance = node.distance + nextNode.weight;
          if (distance < nextNode.distance && nextNode.links.length > 1) {
              nextNode.prev = node;
              nextNode.distance = d;
              queue.push(nextNode);
          }
      }
      i++;
  }
  return cache
};


var graph = [{"id":0,"links":[{"id":6,"weight":70.71067811865476},{"id":1,"weight":810}]},
{"id":1,"links":[{"id":0,"weight":810},{"id":2,"weight":70.71067811865476}]},
{"id":2,"links":[{"id":1,"weight":70.71067811865476},{"id":3,"weight":1592}]},
{"id":3,"links":[{"id":2,"weight":1592},{"id":5,"weight":70.71067811865476},{"id":153,"weight":205.87711451966396}]},
{"id":4,"links":[{"id":7,"weight":70.71067811865476},{"id":112,"weight":512.6115351930363},{"id":153,"weight":737.0774717197235}]},
{"id":5,"links":[{"id":3,"weight":70.71067811865476},{"id":153,"weight":135.6583919878893}]},
{"id":6,"links":[{"id":0,"weight":70.71067811865476},{"id":94,"weight":310.40008748620136}]},
{"id":7,"links":[{"id":4,"weight":70.71067811865476},{"id":94,"weight":1281.6150329914337}]},
{"id":8,"links":[{"id":9,"weight":55.43314410935759},{"id":27,"weight":394.91497146070554},{"id":89,"weight":249.25217498817833},{"id":17,"weight":37.97639596422426}]},
{"id":9,"links":[{"id":8,"weight":55.43314410935759},{"id":10,"weight":62.68381161480822},{"id":85,"weight":257.37611801643203},{"id":119,"weight":357.92609495024175}]},
{"id":10,"links":[{"id":9,"weight":62.68381161480822},{"id":11,"weight":22.00603386355706},{"id":43,"weight":325.893754212365},{"id":95,"weight":145.6349677143284},{"id":114,"weight":495.27154468751036},{"id":157,"weight":475.0410693030716},{"id":159,"weight":424.5428223515612},{"id":160,"weight":386.9207320551183},{"id":161,"weight":293.9650424785912}]},
{"id":11,"links":[{"id":10,"weight":22.00603386355706},{"id":12,"weight":40.754770931103174},{"id":66,"weight":338.44828019294425},{"id":154,"weight":277.7768610143829}]},
{"id":12,"links":[{"id":11,"weight":40.754770931103174},{"id":13,"weight":63.96396957495827},{"id":71,"weight":279.46200199816974},{"id":130,"weight":423.73430144247175},{"id":142,"weight":605.3109163530141}]},
{"id":13,"links":[{"id":12,"weight":63.96396957495827},{"id":14,"weight":42.685329113484585},{"id":22,"weight":267.044681207588},{"id":18,"weight":383.79570105328406},{"id":89,"weight":295.1151050396651},{"id":97,"weight":173.37684490280637},{"id":147,"weight":644.3394809974541}]},
{"id":14,"links":[{"id":13,"weight":42.685329113484585},{"id":15,"weight":45.39123913699872}]},
{"id":15,"links":[{"id":14,"weight":45.39123913699872},{"id":16,"weight":47.047036449194316},{"id":65,"weight":294.0887879580657},{"id":86,"weight":183.6721765115165},{"id":114,"weight":486.6941103104043},{"id":159,"weight":416.3689141062264},{"id":160,"weight":344.37793610826577}]},
{"id":16,"links":[{"id":15,"weight":47.047036449194316},{"id":17,"weight":25.7772200449739},{"id":43,"weight":298.08763602419685},{"id":39,"weight":354.1679638306291},{"id":70,"weight":371.37278825824006},{"id":74,"weight":670.2294043204714},{"id":132,"weight":378.87860482952715},{"id":157,"weight":434.2784913076533},{"id":161,"weight":262.12088923847034}]},
{"id":17,"links":[{"id":16,"weight":25.7772200449739},{"id":8,"weight":37.97639596422426},{"id":22,"weight":283.4489103653117},{"id":136,"weight":499.55002623505305},{"id":142,"weight":589.0762111107545}]},
{"id":18,"links":[{"id":13,"weight":383.79570105328406},{"id":19,"weight":68.56451044560333},{"id":27,"weight":31.90572098820839}]},
{"id":19,"links":[{"id":18,"weight":68.56451044560333},{"id":20,"weight":60.809531997686655},{"id":64,"weight":400.06011580087164},{"id":156,"weight":445.50275071828963}]},
{"id":20,"links":[{"id":19,"weight":60.809531997686655},{"id":21,"weight":41.7268040869492}]},
{"id":21,"links":[{"id":20,"weight":41.7268040869492},{"id":22,"weight":44.409786926805985},{"id":70,"weight":244.19177296204867},{"id":91,"weight":205.16309784978526},{"id":131,"weight":170.98157093493768}]},
{"id":22,"links":[{"id":13,"weight":267.044681207588},{"id":17,"weight":283.4489103653117},{"id":21,"weight":44.409786926805985},{"id":23,"weight":73.41351083187409},{"id":44,"weight":578.7057992684693},{"id":39,"weight":603.7781336207288},{"id":49,"weight":794.3115697606781},{"id":57,"weight":486.1389713865941},{"id":86,"weight":298.95911490661615},{"id":128,"weight":342.80891355908545},{"id":135,"weight":282.6431518625895},{"id":142,"weight":308.1360659862511},{"id":147,"weight":378.58967001309463},{"id":161,"weight":491.24332514971724}]},
{"id":23,"links":[{"id":22,"weight":73.41351083187409},{"id":24,"weight":47.156569853258866},{"id":63,"weight":299.1373917294431},{"id":156,"weight":424.0775352517563}]},
{"id":24,"links":[{"id":23,"weight":47.156569853258866},{"id":25,"weight":86.13825660873893},{"id":131,"weight":210.320160984807}]},
{"id":25,"links":[{"id":24,"weight":86.13825660873893},{"id":26,"weight":33.06353502569152}]},
{"id":26,"links":[{"id":25,"weight":33.06353502569152},{"id":27,"weight":67.91460112401641},{"id":57,"weight":540.3387174980588},{"id":92,"weight":228.93825991593803},{"id":120,"weight":412.75883815805963},{"id":128,"weight":418.9168740031914},{"id":142,"weight":333.7521131385038}]},
{"id":27,"links":[{"id":8,"weight":394.91497146070554},{"id":26,"weight":67.91460112401641},{"id":18,"weight":31.90572098820839},{"id":80,"weight":593.5258503155924},{"id":89,"weight":148.5928396302128},{"id":147,"weight":349.297544643658}]},
{"id":28,"links":[{"id":29,"weight":59.67018420401978},{"id":81,"weight":209.96278270854182},{"id":106,"weight":69.99034725665763},{"id":149,"weight":340.8623984131601},{"id":37,"weight":28.746317165572204}]},
{"id":29,"links":[{"id":28,"weight":59.67018420401978},{"id":30,"weight":23.113480906778186},{"id":60,"weight":155.8179847580466},{"id":77,"weight":297.5407757529884}]},
{"id":30,"links":[{"id":29,"weight":23.113480906778186},{"id":31,"weight":24.194433832360634},{"id":48,"weight":312.87236629082633}]},
{"id":31,"links":[{"id":30,"weight":24.194433832360634},{"id":32,"weight":95.03245812683691},{"id":52,"weight":306.82477443979093},{"id":107,"weight":78.85870804148841}]},
{"id":32,"links":[{"id":31,"weight":95.03245812683691},{"id":33,"weight":28.769841069179858},{"id":60,"weight":147.93878749367386}]},
{"id":33,"links":[{"id":32,"weight":28.769841069179858},{"id":34,"weight":26.884913041414087},{"id":149,"weight":324.73490720293273}]},
{"id":34,"links":[{"id":33,"weight":26.884913041414087},{"id":35,"weight":34.539644671799884},{"id":48,"weight":312.60280041119495},{"id":82,"weight":298.7966839326061}]},
{"id":35,"links":[{"id":34,"weight":34.539644671799884},{"id":36,"weight":47.88309910969351},{"id":52,"weight":298.6492567682363},{"id":78,"weight":270.88254329096384}]},
{"id":36,"links":[{"id":35,"weight":47.88309910969351},{"id":37,"weight":55.92799176338086},{"id":146,"weight":250.2794421195491}]},
{"id":37,"links":[{"id":36,"weight":55.92799176338086},{"id":28,"weight":28.746317165572204},{"id":101,"weight":174.53904785374436}]},
{"id":38,"links":[{"id":45,"weight":41.60346490016386},{"id":160,"weight":259.95392603739697}]},
{"id":39,"links":[{"id":16,"weight":354.1679638306291},{"id":22,"weight":603.7781336207288},{"id":40,"weight":28.56292626279466},{"id":136,"weight":827.1618749297187},{"id":142,"weight":911.9072364060776}]},
{"id":40,"links":[{"id":39,"weight":28.56292626279466},{"id":41,"weight":71.83348433366919},{"id":87,"weight":385.18415791555594}]},
{"id":41,"links":[{"id":40,"weight":71.83348433366919},{"id":42,"weight":25.66448755744104},{"id":84,"weight":301.86449922516306},{"id":119,"weight":304.09006218105435},{"id":160,"weight":191.66415098549578},{"id":161,"weight":42.17582986887332}]},
{"id":42,"links":[{"id":41,"weight":25.66448755744104},{"id":43,"weight":25.041564347271354},{"id":114,"weight":201.32515950767336},{"id":159,"weight":136.50001088374017}]},
{"id":43,"links":[{"id":10,"weight":325.893754212365},{"id":16,"weight":298.08763602419685},{"id":42,"weight":25.041564347271354},{"id":44,"weight":53.81505716045718},{"id":70,"weight":668.6142302142265},{"id":95,"weight":464.5912380083568},{"id":132,"weight":675.2576499747647},{"id":157,"weight":149.3858968154142},{"id":161,"weight":35.96703115932087}]},
{"id":44,"links":[{"id":22,"weight":578.7057992684693},{"id":43,"weight":53.81505716045718},{"id":45,"weight":41.40801209082323},{"id":57,"weight":1063.3996891527247},{"id":136,"weight":809.6193736796965}]},
{"id":45,"links":[{"id":44,"weight":41.40801209082323},{"id":38,"weight":41.60346490016386},{"id":86,"weight":326.14140573310647},{"id":83,"weight":413.3998108385815},{"id":118,"weight":301.0257064648056}]},
{"id":46,"links":[{"id":47,"weight":32.324323407861954},{"id":54,"weight":25.030634943141447}]},
{"id":47,"links":[{"id":46,"weight":32.324323407861954},{"id":48,"weight":74.97098636842881},{"id":150,"weight":482.148526864346}]},
{"id":48,"links":[{"id":30,"weight":312.87236629082633},{"id":34,"weight":312.60280041119495},{"id":47,"weight":74.97098636842881},{"id":49,"weight":51.584467579702824},{"id":61,"weight":244.27972531448285},{"id":106,"weight":336.640487491796}]},
{"id":49,"links":[{"id":22,"weight":794.3115697606781},{"id":48,"weight":51.584467579702824},{"id":57,"weight":308.50551001966323},{"id":128,"weight":451.6465055929891},{"id":135,"weight":511.844500792933}]},
{"id":50,"links":[{"id":51,"weight":49.512416392803104}]},
{"id":51,"links":[{"id":50,"weight":49.512416392803104},{"id":52,"weight":53.04787162699196}]},
{"id":52,"links":[{"id":31,"weight":306.82477443979093},{"id":35,"weight":298.6492567682363},{"id":51,"weight":53.04787162699196},{"id":53,"weight":76.43056418497244},{"id":82,"weight":547.120073731121},{"id":110,"weight":325.05226324305437},{"id":150,"weight":458.3924820628751}]},
{"id":53,"links":[{"id":52,"weight":76.43056418497244},{"id":54,"weight":20.039265191224455}]},
{"id":54,"links":[{"id":53,"weight":20.039265191224455},{"id":46,"weight":25.030634943141447},{"id":58,"weight":244.9260216552532},{"id":67,"weight":756.3463895463947},{"id":76,"weight":482.3227102069046},{"id":124,"weight":422.2533744531271}]},
{"id":55,"links":[{"id":56,"weight":58.460583239231624},{"id":102,"weight":115.82406310298205},{"id":125,"weight":152.5815324765102}]},
{"id":56,"links":[{"id":55,"weight":58.460583239231624},{"id":57,"weight":55.57519143003837}]},
{"id":57,"links":[{"id":22,"weight":486.1389713865941},{"id":26,"weight":540.3387174980588},{"id":44,"weight":1063.3996891527247},{"id":49,"weight":308.50551001966323},{"id":56,"weight":55.57519143003837},{"id":58,"weight":48.45767081071381},{"id":158,"weight":180.39992938539922},{"id":136,"weight":253.7803363149803},{"id":142,"weight":206.67779462996376}]},
{"id":58,"links":[{"id":54,"weight":244.9260216552532},{"id":57,"weight":48.45767081071381},{"id":59,"weight":24.092997373752972}]},
{"id":59,"links":[{"id":58,"weight":24.092997373752972},{"id":60,"weight":82.39211060953677},{"id":76,"weight":268.66979964854914},{"id":124,"weight":204.95995317424766}]},
{"id":60,"links":[{"id":29,"weight":155.8179847580466},{"id":32,"weight":147.93878749367386},{"id":59,"weight":82.39211060953677},{"id":61,"weight":56.8386682833888}]},
{"id":61,"links":[{"id":48,"weight":244.27972531448285},{"id":60,"weight":56.8386682833888},{"id":77,"weight":395.3342593777817},{"id":106,"weight":94.82870098367673}]},
{"id":62,"links":[{"id":63,"weight":50.239660941572126},{"id":138,"weight":456.67384076187767},{"id":71,"weight":38.53358308507445}]},
{"id":63,"links":[{"id":23,"weight":299.1373917294431},{"id":62,"weight":50.239660941572126},{"id":64,"weight":49.29188012559735}]},
{"id":64,"links":[{"id":19,"weight":400.06011580087164},{"id":63,"weight":49.29188012559735},{"id":65,"weight":34.9390920450358},{"id":91,"weight":484.70495246456426}]},
{"id":65,"links":[{"id":15,"weight":294.0887879580657},{"id":64,"weight":34.9390920450358},{"id":66,"weight":44.386933593419634},{"id":86,"weight":473.4945906187595},{"id":160,"weight":638.3194987663459}]},
{"id":66,"links":[{"id":11,"weight":338.44828019294425},{"id":65,"weight":44.386933593419634},{"id":67,"weight":46.35007638082747},{"id":97,"weight":354.99096425656126},{"id":155,"weight":98.46201480548129}]},
{"id":67,"links":[{"id":54,"weight":756.3463895463947},{"id":66,"weight":46.35007638082747},{"id":68,"weight":83.11118143775956},{"id":76,"weight":275.22916188389814},{"id":124,"weight":334.3275404295602}]},
{"id":68,"links":[{"id":67,"weight":83.11118143775956},{"id":69,"weight":61.82288775247714}]},
{"id":69,"links":[{"id":68,"weight":61.82288775247714},{"id":70,"weight":32.72720780632854}]},
{"id":70,"links":[{"id":16,"weight":371.37278825824006},{"id":21,"weight":244.19177296204867},{"id":43,"weight":668.6142302142265},{"id":69,"weight":32.72720780632854},{"id":71,"weight":82.01328044192185},{"id":74,"weight":299.3033974268629},{"id":86,"weight":467.8800531253375},{"id":114,"weight":795.7351820979673},{"id":131,"weight":74.14997079035552},{"id":157,"weight":798.2577975693512},{"id":159,"weight":728.6111329180097},{"id":161,"weight":632.6993752105095}]},
{"id":71,"links":[{"id":12,"weight":279.46200199816974},{"id":70,"weight":82.01328044192185},{"id":62,"weight":38.53358308507445},{"id":97,"weight":376.4367138297526},{"id":122,"weight":299.55665657848795},{"id":132,"weight":92.36209904758263},{"id":131,"weight":67.09223542194184},{"id":156,"weight":229.10251215735252}]},
{"id":72,"links":[{"id":73,"weight":22.44295867376786},{"id":124,"weight":96.7927637387651},{"id":76,"weight":30.383770443458943}]},
{"id":73,"links":[{"id":72,"weight":22.44295867376786}]},
{"id":74,"links":[{"id":16,"weight":670.2294043204714},{"id":70,"weight":299.3033974268629},{"id":75,"weight":41.39428112635902},{"id":121,"weight":140.7096972711017},{"id":132,"weight":291.38771611392053}]},
{"id":75,"links":[{"id":74,"weight":41.39428112635902},{"id":76,"weight":30.0627689482037}]},
{"id":76,"links":[{"id":54,"weight":482.3227102069046},{"id":59,"weight":268.66979964854914},{"id":67,"weight":275.22916188389814},{"id":75,"weight":30.0627689482037},{"id":72,"weight":30.383770443458943}]},
{"id":77,"links":[{"id":29,"weight":297.5407757529884},{"id":61,"weight":395.3342593777817},{"id":78,"weight":52.00968489404878},{"id":106,"weight":300.6735447670068},{"id":145,"weight":213.64883986492893}]},
{"id":78,"links":[{"id":35,"weight":270.88254329096384},{"id":77,"weight":52.00968489404878},{"id":79,"weight":44.23783407847146}]},
{"id":79,"links":[{"id":78,"weight":44.23783407847146},{"id":80,"weight":38.118361538425795}]},
{"id":80,"links":[{"id":27,"weight":593.5258503155924},{"id":79,"weight":38.118361538425795},{"id":81,"weight":88.22727131494065},{"id":92,"weight":748.610228678086},{"id":117,"weight":922.5836952812741},{"id":160,"weight":981.0925983047125}]},
{"id":81,"links":[{"id":28,"weight":209.96278270854182},{"id":80,"weight":88.22727131494065},{"id":82,"weight":65.51209274182104},{"id":101,"weight":323.12731048143235},{"id":147,"weight":350.10072558836436}]},
{"id":82,"links":[{"id":34,"weight":298.7966839326061},{"id":52,"weight":547.120073731121},{"id":81,"weight":65.51209274182104},{"id":111,"weight":269.9434631344396}]},
{"id":83,"links":[{"id":45,"weight":413.3998108385815},{"id":84,"weight":49.04899812555336},{"id":92,"weight":30.837464050468025}]},
{"id":84,"links":[{"id":41,"weight":301.86449922516306},{"id":83,"weight":49.04899812555336},{"id":85,"weight":63.71188304619065},{"id":161,"weight":262.445211274406}]},
{"id":85,"links":[{"id":9,"weight":257.37611801643203},{"id":84,"weight":63.71188304619065},{"id":86,"weight":49.09351203637654}]},
{"id":86,"links":[{"id":15,"weight":183.6721765115165},{"id":22,"weight":298.95911490661615},{"id":45,"weight":326.14140573310647},{"id":65,"weight":473.4945906187595},{"id":70,"weight":467.8800531253375},{"id":85,"weight":49.09351203637654},{"id":87,"weight":83.46480593410709},{"id":119,"weight":151.90228469087668},{"id":114,"weight":329.0079671927419},{"id":128,"weight":641.7308695509025},{"id":132,"weight":471.07620316344014},{"id":135,"weight":581.5450583764579},{"id":157,"weight":337.27659265236},{"id":159,"weight":264.5824947674739},{"id":160,"weight":170.91599639926625}]},
{"id":87,"links":[{"id":40,"weight":385.18415791555594},{"id":86,"weight":83.46480593410709},{"id":88,"weight":41.619088536378854},{"id":161,"weight":285.65519727136444}]},
{"id":88,"links":[{"id":87,"weight":41.619088536378854},{"id":89,"weight":19.022840656019405}]},
{"id":89,"links":[{"id":8,"weight":249.25217498817833},{"id":13,"weight":295.1151050396651},{"id":27,"weight":148.5928396302128},{"id":88,"weight":19.022840656019405},{"id":90,"weight":35.841603038774416}]},
{"id":90,"links":[{"id":89,"weight":35.841603038774416},{"id":91,"weight":32.398612793756314}]},
{"id":91,"links":[{"id":21,"weight":205.16309784978526},{"id":64,"weight":484.70495246456426},{"id":90,"weight":32.398612793756314},{"id":92,"weight":48.582975729764854}]},
{"id":92,"links":[{"id":26,"weight":228.93825991593803},{"id":80,"weight":748.610228678086},{"id":91,"weight":48.582975729764854},{"id":83,"weight":30.837464050468025},{"id":120,"weight":188.7591372909066},{"id":117,"weight":174.02812344524793},{"id":146,"weight":572.3906052533645},{"id":159,"weight":344.37896644057383},{"id":160,"weight":232.48237745520552}]},
{"id":93,"links":[{"id":97,"weight":102.0522575060609}]},
{"id":94,"links":[{"id":6,"weight":310.40008748620136},{"id":7,"weight":1281.6150329914337}]},
{"id":95,"links":[{"id":10,"weight":145.6349677143284},{"id":43,"weight":464.5912380083568},{"id":96,"weight":20.309465539051313},{"id":114,"weight":637.3889554757393},{"id":159,"weight":567.3380419121927},{"id":161,"weight":434.67294753052647}]},
{"id":96,"links":[{"id":95,"weight":20.309465539051313},{"id":97,"weight":63.213233743350074}]},
{"id":97,"links":[{"id":13,"weight":173.37684490280637},{"id":66,"weight":354.99096425656126},{"id":71,"weight":376.4367138297526},{"id":96,"weight":63.213233743350074},{"id":93,"weight":102.0522575060609},{"id":100,"weight":240.91712277511493},{"id":130,"weight":525.9007129529984},{"id":142,"weight":709.2888517760487},{"id":147,"weight":817.6275336689539},{"id":155,"weight":256.52958550596395}]},
{"id":98,"links":[{"id":99,"weight":38.26238414408713}]},
{"id":99,"links":[{"id":98,"weight":38.26238414408713},{"id":100,"weight":81.55030224358033}]},
{"id":100,"links":[{"id":97,"weight":240.91712277511493},{"id":99,"weight":81.55030224358033},{"id":130,"weight":766.6709881560315},{"id":142,"weight":949.697709689759}]},
{"id":101,"links":[{"id":37,"weight":174.53904785374436},{"id":81,"weight":323.12731048143235},{"id":102,"weight":47.30056869901373},{"id":143,"weight":92.85603330225935},{"id":109,"weight":48.22919045283958}]},
{"id":102,"links":[{"id":55,"weight":115.82406310298205},{"id":101,"weight":47.30056869901373},{"id":103,"weight":35.380667355785846},{"id":125,"weight":257.26089278078433},{"id":145,"weight":86.69660180432261}]},
{"id":103,"links":[{"id":102,"weight":35.380667355785846},{"id":104,"weight":43.58038875739012}]},
{"id":104,"links":[{"id":103,"weight":43.58038875739012}]},
{"id":105,"links":[{"id":106,"weight":49.00253118207074}]},
{"id":106,"links":[{"id":28,"weight":69.99034725665763},{"id":48,"weight":336.640487491796},{"id":61,"weight":94.82870098367673},{"id":77,"weight":300.6735447670068},{"id":105,"weight":49.00253118207074},{"id":107,"weight":27.405833077229865}]},
{"id":107,"links":[{"id":31,"weight":78.85870804148841},{"id":106,"weight":27.405833077229865},{"id":108,"weight":39.67467085048693},{"id":146,"weight":161.5285374896578}]},
{"id":108,"links":[{"id":107,"weight":39.67467085048693},{"id":109,"weight":28.034817769574357}]},
{"id":109,"links":[{"id":108,"weight":28.034817769574357},{"id":101,"weight":48.22919045283958}]},
{"id":110,"links":[{"id":52,"weight":325.05226324305437},{"id":111,"weight":25.375224080516592},{"id":150,"weight":133.5176916667986}]},
{"id":111,"links":[{"id":82,"weight":269.9434631344396},{"id":110,"weight":25.375224080516592}]},
{"id":112,"links":[{"id":4,"weight":512.6115351930363},{"id":113,"weight":83.28092580028589},{"id":153,"weight":239.32930481887956}]},
{"id":113,"links":[{"id":112,"weight":83.28092580028589}]},
{"id":114,"links":[{"id":10,"weight":495.27154468751036},{"id":15,"weight":486.6941103104043},{"id":42,"weight":201.32515950767336},{"id":70,"weight":795.7351820979673},{"id":86,"weight":329.0079671927419},{"id":95,"weight":637.3889554757393},{"id":115,"weight":101.77827438406392},{"id":132,"weight":799.5716987622106},{"id":159,"weight":71.39727162164735},{"id":161,"weight":202.98164149753293}]},
{"id":115,"links":[{"id":114,"weight":101.77827438406392},{"id":116,"weight":55.33658324913234},{"id":160,"weight":63.25551243883601}]},
{"id":116,"links":[{"id":115,"weight":55.33658324913234},{"id":117,"weight":64.34602362067791}]},
{"id":117,"links":[{"id":80,"weight":922.5836952812741},{"id":92,"weight":174.02812344524793},{"id":116,"weight":64.34602362067791},{"id":118,"weight":25.616725172113455},{"id":157,"weight":242.8128909397011},{"id":159,"weight":170.35193802012466},{"id":160,"weight":58.715883663506396}]},
{"id":118,"links":[{"id":45,"weight":301.0257064648056},{"id":117,"weight":25.616725172113455},{"id":119,"weight":49.34327971363866}]},
{"id":119,"links":[{"id":9,"weight":357.92609495024175},{"id":41,"weight":304.09006218105435},{"id":86,"weight":151.90228469087668},{"id":118,"weight":49.34327971363866},{"id":120,"weight":92.13543408276188},{"id":161,"weight":262.52409073917073}]},
{"id":120,"links":[{"id":26,"weight":412.75883815805963},{"id":92,"weight":188.7591372909066},{"id":119,"weight":92.13543408276188}]},
{"id":121,"links":[{"id":74,"weight":140.7096972711017},{"id":122,"weight":49.158380910815055}]},
{"id":122,"links":[{"id":71,"weight":299.55665657848795},{"id":121,"weight":49.158380910815055},{"id":123,"weight":22.072670207307805},{"id":132,"weight":207.55080569931508}]},
{"id":123,"links":[{"id":122,"weight":22.072670207307805},{"id":124,"weight":23.95147516157658}]},
{"id":124,"links":[{"id":54,"weight":422.2533744531271},{"id":59,"weight":204.95995317424766},{"id":67,"weight":334.3275404295602},{"id":72,"weight":96.7927637387651},{"id":123,"weight":23.95147516157658},{"id":125,"weight":37.10612238764236}]},
{"id":125,"links":[{"id":55,"weight":152.5815324765102},{"id":102,"weight":257.26089278078433},{"id":124,"weight":37.10612238764236},{"id":126,"weight":34.927378155183234},{"id":141,"weight":258.1518700205428}]},
{"id":126,"links":[{"id":125,"weight":34.927378155183234},{"id":127,"weight":32.98615477724716}]},
{"id":127,"links":[{"id":126,"weight":32.98615477724716},{"id":128,"weight":16.22742340952728}]},
{"id":128,"links":[{"id":22,"weight":342.80891355908545},{"id":26,"weight":418.9168740031914},{"id":49,"weight":451.6465055929891},{"id":86,"weight":641.7308695509025},{"id":127,"weight":16.22742340952728},{"id":158,"weight":35.94532649063341},{"id":135,"weight":60.199671727187834}]},
{"id":129,"links":[]},
{"id":130,"links":[{"id":12,"weight":423.73430144247175},{"id":97,"weight":525.9007129529984},{"id":100,"weight":766.6709881560315},{"id":131,"weight":89.63249969243708},{"id":137,"weight":44.67921793243463}]},
{"id":131,"links":[{"id":21,"weight":170.98157093493768},{"id":24,"weight":210.320160984807},{"id":70,"weight":74.14997079035552},{"id":71,"weight":67.09223542194184},{"id":130,"weight":89.63249969243708},{"id":132,"weight":70.44518620133896},{"id":142,"weight":273.78551731820147},{"id":138,"weight":351.5407196157602},{"id":156,"weight":296.14115910691856}]},
{"id":132,"links":[{"id":16,"weight":378.87860482952715},{"id":43,"weight":675.2576499747647},{"id":71,"weight":92.36209904758263},{"id":74,"weight":291.38771611392053},{"id":86,"weight":471.07620316344014},{"id":114,"weight":799.5716987622106},{"id":122,"weight":207.55080569931508},{"id":131,"weight":70.44518620133896},{"id":133,"weight":53.20257740632008},{"id":157,"weight":803.2044974295419},{"id":159,"weight":733.0042344492691},{"id":161,"weight":639.4014374495188}]},
{"id":133,"links":[{"id":132,"weight":53.20257740632008},{"id":134,"weight":50.32148162147291}]},
{"id":134,"links":[{"id":133,"weight":50.32148162147291}]},
{"id":135,"links":[{"id":22,"weight":282.6431518625895},{"id":49,"weight":511.844500792933},{"id":86,"weight":581.5450583764579},{"id":128,"weight":60.199671727187834},{"id":136,"weight":49.49620942581232}]},
{"id":136,"links":[{"id":17,"weight":499.55002623505305},{"id":39,"weight":827.1618749297187},{"id":44,"weight":809.6193736796965},{"id":57,"weight":253.7803363149803},{"id":135,"weight":49.49620942581232},{"id":137,"weight":31.43818529653531},{"id":161,"weight":721.2341683340406}]},
{"id":137,"links":[{"id":136,"weight":31.43818529653531},{"id":130,"weight":44.67921793243463}]},
{"id":138,"links":[{"id":62,"weight":456.67384076187767},{"id":131,"weight":351.5407196157602},{"id":139,"weight":23.777001819899976},{"id":156,"weight":645.5864796077194},{"id":147,"weight":60.21879922428856}]},
{"id":139,"links":[{"id":138,"weight":23.777001819899976},{"id":140,"weight":47.7270317027185}]},
{"id":140,"links":[{"id":139,"weight":47.7270317027185},{"id":141,"weight":23.039143895070726}]},
{"id":141,"links":[{"id":125,"weight":258.1518700205428},{"id":140,"weight":23.039143895070726},{"id":142,"weight":70.27931275561932}]},
{"id":142,"links":[{"id":12,"weight":605.3109163530141},{"id":17,"weight":589.0762111107545},{"id":22,"weight":308.1360659862511},{"id":26,"weight":333.7521131385038},{"id":39,"weight":911.9072364060776},{"id":57,"weight":206.67779462996376},{"id":97,"weight":709.2888517760487},{"id":100,"weight":949.697709689759},{"id":131,"weight":273.78551731820147},{"id":141,"weight":70.27931275561932},{"id":143,"weight":64.98383750211529}]},
{"id":143,"links":[{"id":101,"weight":92.85603330225935},{"id":142,"weight":64.98383750211529},{"id":144,"weight":30.097551026293797}]},
{"id":144,"links":[{"id":143,"weight":30.097551026293797},{"id":145,"weight":100.10632073495346}]},
{"id":145,"links":[{"id":77,"weight":213.64883986492893},{"id":102,"weight":86.69660180432261},{"id":144,"weight":100.10632073495346},{"id":146,"weight":43.76422694558446}]},
{"id":146,"links":[{"id":36,"weight":250.2794421195491},{"id":92,"weight":572.3906052533645},{"id":107,"weight":161.5285374896578},{"id":145,"weight":43.76422694558446},{"id":147,"weight":62.554721469410964}]},
{"id":147,"links":[{"id":13,"weight":644.3394809974541},{"id":22,"weight":378.58967001309463},{"id":27,"weight":349.297544643658},{"id":81,"weight":350.10072558836436},{"id":97,"weight":817.6275336689539},{"id":146,"weight":62.554721469410964},{"id":138,"weight":60.21879922428856}]},
{"id":148,"links":[{"id":153,"weight":83.09197814327331}]},
{"id":149,"links":[{"id":28,"weight":340.8623984131601},{"id":33,"weight":324.73490720293273},{"id":150,"weight":40.27917844217807}]},
{"id":150,"links":[{"id":47,"weight":482.148526864346},{"id":52,"weight":458.3924820628751},{"id":110,"weight":133.5176916667986},{"id":149,"weight":40.27917844217807}]},
{"id":151,"links":[{"id":152,"weight":16.05179269405632}]},
{"id":152,"links":[{"id":151,"weight":16.05179269405632},{"id":153,"weight":95.08995160516936}]},
{"id":153,"links":[{"id":3,"weight":205.87711451966396},{"id":4,"weight":737.0774717197235},{"id":5,"weight":135.6583919878893},{"id":112,"weight":239.32930481887956},{"id":152,"weight":95.08995160516936},{"id":148,"weight":83.09197814327331}]},
{"id":154,"links":[{"id":11,"weight":277.7768610143829},{"id":155,"weight":33.19341980748434}]},
{"id":155,"links":[{"id":66,"weight":98.46201480548129},{"id":97,"weight":256.52958550596395},{"id":154,"weight":33.19341980748434},{"id":156,"weight":58.397228717203404}]},
{"id":156,"links":[{"id":19,"weight":445.50275071828963},{"id":23,"weight":424.0775352517563},{"id":71,"weight":229.10251215735252},{"id":131,"weight":296.14115910691856},{"id":138,"weight":645.5864796077194},{"id":155,"weight":58.397228717203404}]},
{"id":157,"links":[{"id":10,"weight":475.0410693030716},{"id":16,"weight":434.2784913076533},{"id":43,"weight":149.3858968154142},{"id":70,"weight":798.2577975693512},{"id":86,"weight":337.27659265236},{"id":117,"weight":242.8128909397011},{"id":132,"weight":803.2044974295419}]},
{"id":158,"links":[{"id":57,"weight":180.39992938539922},{"id":128,"weight":35.94532649063341},{"id":160,"weight":44.1282092957909}]},
{"id":159,"links":[{"id":10,"weight":424.5428223515612},{"id":15,"weight":416.3689141062264},{"id":42,"weight":136.50001088374017},{"id":70,"weight":728.6111329180097},{"id":86,"weight":264.5824947674739},{"id":92,"weight":344.37896644057383},{"id":95,"weight":567.3380419121927},{"id":117,"weight":170.35193802012466},{"id":114,"weight":71.39727162164735},{"id":132,"weight":733.0042344492691},{"id":160,"weight":112.12052199347016},{"id":161,"weight":134.34656675925888}]},
{"id":160,"links":[{"id":10,"weight":386.9207320551183},{"id":15,"weight":344.37793610826577},{"id":38,"weight":259.95392603739697},{"id":41,"weight":191.66415098549578},{"id":65,"weight":638.3194987663459},{"id":80,"weight":981.0925983047125},{"id":86,"weight":170.91599639926625},{"id":92,"weight":232.48237745520552},{"id":117,"weight":58.715883663506396},{"id":115,"weight":63.25551243883601},{"id":158,"weight":44.1282092957909},{"id":159,"weight":112.12052199347016}]},
{"id":161,"links":[{"id":10,"weight":293.9650424785912},{"id":16,"weight":262.12088923847034},{"id":22,"weight":491.24332514971724},{"id":43,"weight":35.96703115932087},{"id":41,"weight":42.17582986887332},{"id":70,"weight":632.6993752105095},{"id":87,"weight":285.65519727136444},{"id":84,"weight":262.445211274406},{"id":95,"weight":434.67294753052647},{"id":119,"weight":262.52409073917073},{"id":114,"weight":202.98164149753293},{"id":132,"weight":639.4014374495188},{"id":136,"weight":721.2341683340406},{"id":159,"weight":134.34656675925888}]}]


var get_path = function(graph, a) {
// declaration
  let cache, i, v, queue, node, links, root,
      j, link, c, n, d, max, w, L = graph.length;

  // initialization
  cache = Array(L);
  i = L;
  while (--i >= 0) {
      v = graph[i];
      cache[v.id] = {
          id: v.id,
          distance: Infinity,
          links: v.links,
          prev: null,
      };
  }
  root = cache[a];
  root.distance = 0;
  queue = [root];

  // processing
  i = 0;
  while (i < queue.length) {
      node = queue[i];
      links = node.links;
      j = links.length;
      while (--j >= 0) {
          link = links[j];
          c = cache[link.id];
          d = node.distance + link.weight;
          if (d < c.distance) {
              c.prev = node;
              c.distance = d;
              queue.push(c);
          }
      }
      i++;
  }

  return cache
};

var times = [], newTimes = [];

for (let i=0; i < 1000; i++) {
  var s_t = performance.now();
  res = get_path(graph, 157);
  times.push(performance.now() - s_t);
}

for (let i=0; i < 1000; i++) {
  var s_t = performance.now();
  res = getDistancesFromNode(graph, 157);
  newTimes.push(performance.now() - s_t);
}


function average(nums) {
    return nums.reduce((a, b) => (a + b)) / nums.length;
}

console.log(average(times), 'ms')
console.log(average(newTimes), 'ms')

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ what's wrong with variable name? And can you tell me more details about optimization to make it faster? I should use graph instead of cache? I am afriad, that it will broke the algorithm. \$\endgroup\$
    – Данил Черкашин
    Feb 4, 2021 at 23:43
  • \$\begingroup\$ I rewrote with better variable names, I hope you can appreciate the difference in readability. \$\endgroup\$
    – konijn
    Feb 5, 2021 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.