Social Media Mining: An Introduction

P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38

36 Graph Essentials

Algorithm 2.4Dijkstra’s Shortest Path Algorithm

Require: Start nodes, weighted graph/treeG:(V,E,W)

1: return Shortest paths and distances fromsto all other nodes.

2: forv∈Vdo

3: distance[v]=∞;

4: predecessor[v]=−1;

5: end for

6: distance[s]=0;

7: unvisited=V;

8: whileunvisited =∅do

9: smallest=arg minv∈unvisiteddistance(v);

10: ifdistance(smallest)==∞then

11: break;

12: end if

13: unvisited=unvisited\{smallest};

14: currentDistance=distance(smallest);

15: foradjacent node tosmallest:neighbor∈unvisited do

16: newPath=currentDistance+w(smallest,neighbor);

17: ifnewPath<distance(neighbor)then

18: distance(neighbor)=newPath;

19: predecessor(neighbor)=smallest;

20: end if

21: end for

22: end while

23: Returndistance[] andpredecessor[] arrays

This can be performed by comparing its current shortest path length

(distance(neighbor)) to the path length that goes throughsmall-

est(distance(smallest)+w(smallest,neighbor)). This condition is

checked in Line 17.

3. If the current shortest path can be improved, the path and its length
   are updated. The paths are saved based on predecessors in the path
   sequence. Since, for every node, we only need the predecessor to
   reconstruct a path recursively, thepredecessorarray keeps track of
   this.


4. A node is marked as visited after all its neighbors are processed and
   is no longer changed in terms of (1) the shortest path that ends with
   it and (2) its shortest path length.