Note: I assume that the OP is talking about Algorithm 1 in the paper "A Faster Algorithm for Betweenness Centrality" By Ulrik Brandes.
You probably have noticed that Algorithm 1 in the paper is for unweighted graphs. In this case, Dijkstra's algorithm@wiki amounts to BFS and a shortest path for a vertex $v$ is found immediately when $v$ is first encountered (in the pseudo-code, it is represented by if d[w] < 0 then
). This property is due to the layer-by-layer search feature of BFS.
$Q_1:$ If a node is the first occurrence , then we have to check d[neighbor_node] < 0
. However, if not, do we have to check d[neighbor_node] > d[current] + length(current,neighbor_node)
?
For weighted graphs, the property mentioned above does not necessarily hold. So you need to replace (meaning the following is not needed any more) the if d[w] < 0 then
predicate by a slightly involved one suitable for weighted graphs:
[foreach] neighbor w of v [do] [if] d[v] + length(w,v) < d[w] [then]
Note that for weighted graph, you should use a priority queue.
$Q_2:$ If greater, then do I have to delete previous updates like Queue, Pre[]
and others?
No. You set d[], P[], sigma[]
only when a shortest path is found. It is valid all the time once it is set. No need to update them later.