weighted graphs column by column in the shortest-path array now the algorithm knows not only all the edges from abut the edges from as well so it goes through the shortest-path arraycolumn by columnchecking whether shorter path than that shown can be calculated using this new information vertices that are already in the treehere and bare skipped firstcolumn is examined you'll see the message to ca to ( plus edge bc ( less than to (infthe algorithm has found shorter path to than that shown in the array the array shows infinity in the column but from to is (which the algorithm finds in the column in the shortest-path arrayand from to is (which it finds in row column in the adjacency matrixthe sum is the distance is less than infinityso the algorithm updates the shortest-path array for column cinserting this is followed by in parenthesesbecause that' the last vertex before reaching cb is the parent of nextthe column is examined you'll see the message to da to ( plus edge bd ( greater than or equal to to ( the algorithm is comparing the previously shown distance from to dwhich is (the direct route)with possible route via (that isa- -dbut path - is and edge bd is so the sum is this is bigger than so is not changed for column ethe message is to ea to ( plus edge be (infgreater than or equal to to (infthe newly calculated route from to via ( plus infinityis still greater than or equal to the current one in the array (infinity)so the column is not changed the shortest-path array now looks like table table step the shortest-path array inf( ( ( (ainf(anow we can see more clearly the role played by the parent vertex shown in parentheses after each distance each column shows the distance from to an ending vertex the parent is the immediate predecessor of the ending vertex along the path from in column cthe parent vertex is bmeaning that the shortest path from to passes through just before it gets to this information is used by the algorithm to place the appropriate edge in the tree (when the distance is infinitythe parent vertex is meaningless and is shown as