Question 350634 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How prefix sum logic works in graph minimum distance calculation?

Given an integer n that represents the number of vertices on a graph, and each vertex connect one another with single edge, except for the start vertex and end vertex, we can calculate the minimum distance pair of vertices with the following code. Assuming this is unweighted graph, or can be assumed also weighted graph will all edge weight is 1.

function countMinDistance (n) {
  const result = new Array(n).fill(0)

  for (let i = 0; i < n - 1; i++) {
    result[0] += 2
    result[n - i + 1] -= 2
  }

  for (let i = 0; i + 1 < n; i++) {
    // calculate distance to other nodes with prefix sum of the previous nodes
    result[i + 1] += result[i]
  }

  return result
};

Example for following graph:

(1) --- (2) --- (3) --- (4)

The result of min distance would be an array [6, 4, 2, 0]. Where 6 is total of vertices pairs with min distance of 1, 4 is total vertices pairs with min distance of 2, 2 is total vertices pairs with min distance of 3, 0 is total vertices pairs with min distance of 4.

For each minimum distance k, the pairs are:

  • For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3).
  • For k == 2, the pairs are (1, 3), (3, 1), (2, 4), and (4, 2).
  • For k == 3, the pairs are (1, 4), and (4, 1).
  • For k == 4, there are no pairs.

I understand that on traversing vertices we need to increase by 2, which most likely the distance between current node (vertex) with the previous one multiplied by 2. I also have some understanding that on traversing we need to update distance between current node to all other nodes on the graph. Somehow I didn’t get the efficient way yet to do this in a linear for loop (O(n)) way, until I see the above code. I can do it easily using two nested for loops (or even three nested for loops, with Floyd-Warshall algorithm) though. But because of the execution time constraint, I can’t use it.

The problem is I don’t understand these code parts result[n - i + 1] -= 2 and result[i + 1] += result[i]. Can someone explain how the above code can work for the min distance calculation, especially those parts that I am not sure about? How come when traversing vertices we calculate with decreasing by 2 (what is logical explanation to that, that can be easily reason about?), then doing the prefix sum magic on the second loop, and finally get correct result?

Tags:

2

Answers


  1. 0

    Initialization: Correctly initialize the counts for distances. For a chain of n vertices, the number of pairs at each distance k (from 1 to n-1) follows a specific pattern that needs to be calculated directly, considering the graph’s linear structure.

    Accumulation: Use the correct logic to accumulate these distances. For a linear graph, the pattern is simpler and does not typically require decrementing counts as originally coded.

    Given the misunderstanding in the original code and explanation, a corrected approach focusing on directly calculating distances based on the graph’s linear structure would be more straightforward and accurate. Let’s implement a corrected version based on understanding the problem correctly.

    The corrected approach calculates the minimum distances between pairs of vertices accurately for a linear graph structure. For the example graph with n = 4 vertices:

    The resulting array is [6, 4, 2, 0], which matches the expected outcome.
    This means:

    There are 6 pairs of vertices at a minimum distance of 1 (each adjacent pair, counted in both directions).
    There are 4 pairs of vertices at a minimum distance of 2.
    There are 2 pairs of vertices at a minimum distance of 3.
    There are 0 pairs of vertices at a minimum distance of 4, since the maximum distance in a graph with 4 vertices is 3.

    Login or Signup to reply.
  2. 0

    that code simply is not correct so you cannot understand that.

    let me explain:

    function countMinDistance (n) {
  //here result is initialized as an array of n elements all setted at 0
  //====================================================================
  const result = new Array(n).fill(0);
  //====================================================================

  for (let i = 0; i < n - 1; i++) {
    result[0] += 2
    
    /*
    ===================================================================
    ===================================================================
    ===================================================================
    here on first iteration when i=0 you have result[n+1]-=2
    this is so wrong because n+1 is out of range 
    now the worst part:
      javascript (does not rise an error because it is one of many ways for extend an array ) create 2 other element at the end of your array (2 because even result[n] is out of range)
    and the worst worst part:
      the 2 elements created are not yet initialized so  the "-=2" will  set those element to NaN (Not a Number)
    ===================================================================
    ===================================================================
    ===================================================================
    */
    result[n - i + 1] -= 2;
  }

  for (let i = 0; i + 1 < n; i++) {
    // calculate distance to other nodes with prefix sum of the previous nodes
    result[i + 1] += result[i]
  }

  return result
};
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search