1
if (!require("igraph")) {
2
    install.packages("igraph")
3
    library(igraph)
4
}

1
## Loading required package: igraph
2

3
##
4
## Attaching package: 'igraph'
5

6
## The following objects are masked from 'package:stats':
7
##
8
##     decompose, spectrum
9

10
## The following object is masked from 'package:base':
11
##
12
##     union

1
# regular min() will just get the min distance, not the associated vertex
2
# return the v w/ min dist in Q
3
get_min = function(Q, dist){
4
    d = Inf
5
    v = NA
6
    for(i in 1:length(Q)){
7
    if(as.numeric(dist[1, as.character(Q[i])]) < d){ # new smallest distance
8
        v = as.character(Q[i])
9
        d = dist[1,as.character(Q[i])]
10
    }
11
    }
12
    return(v)
13
}
14

15
# return 'Q' without 'u'
16
del = function(Q, u){
17
    new_Q = list()
18
    pos = 1
19
    for(i in 1:length(Q)){
20
    if(as.character(Q[i]) != u){
21
        # add the element to new_Q
22
        new_Q[pos] = Q[i]
23
        pos = pos + 1
24
    } # else, is 'u', don't add
25
    }
26
    return(new_Q)
27
}
28

29
# get the neighbors of 'u' in the graph 'G' that are still in 'Q'
30
get_neighbors = function(G, u, Q){
31
    n = neighbors(G, u)
32
    res = list()
33
    pos = 1
34
    # for each element in Q
35
    for(i in 1:length(Q)){
36
    # check if it's one of the neighbors
37
    for(v in n$name){
38
        if(as.character(Q[i]) == v){
39
        # is neighbor
40
        res[pos] = v
41
        pos = pos + 1
42
        }
43
    }
44
    }
45
    return(res)
46
}
47

48
# Dijkstra's algorithm
49
dijkstra = function(G, start){
50
    # set up
51
    Q = list()
52
    # n x 1 data frames
53
    dist = data.frame(row.names=V(G)$name)
54
    prev = data.frame(row.names=V(G)$name)
55
    for(v in V(G)$name){
56
    dist[1,v] = Inf
57
    prev[1,v] = NA
58
    Q[length(Q) + 1] = v
59
    }
60
    # initial value
61
    dist[1,start] = 0
62
    # until Q is empty
63
    while(length(Q) > 0){
64
    u = get_min(Q, dist)
65
    Q = del(Q, u)
66
    # if Q is empty, then 'u' is the last element
67
    if(length(Q) != 0){
68
        n = get_neighbors(G, u, Q)
69
        for(v in n){
70
        alt = dist[1,u] + 1 # distance between neighbors is 1, since edges un-weighted
71
        if(alt < dist[1,v]){
72
            dist[1,v] = alt
73
            prev[1,v] = u
74
        }
75
        }
76
    }
77

78
    }
79
    return(data.frame(c(dist, prev)))
80
}
81

82
# set up Q2 graph
83
edges2 = c("x1", "x2",
84
            "x2", "x1",
85
            "x2", "x3",
86
            "x2", "x4",
87
            "x3", "x6",
88
            "x4", "x3",
89
            "x6", "x5",
90
            "x5", "x1")
91
G2 = make_graph(edges2, directed = TRUE)
92
plot(G2)

1
res = dijkstra(G2, "x1")
2
# the distances are:
3
res[1,1:6]

1
##   x1 x2 x3 x4 x6 x5
2
## 1  0  1  2  2  3  4

1
# the previous nodes are:
2
res[1,7:12]

1
##   x1.1 x2.1 x3.1 x4.1 x6.1 x5.1
2
## 1   NA   x1   x2   x2   x3   x6

1
# the paths from 'x1' to any other node is:
2
shortest_paths(G2, "x1", algorithm = "dijkstra")$vpath

1
## [[1]]
2
## + 1/6 vertex, named, from 5af2854:
3
## [1] x1
4
##
5
## [[2]]
6
## + 2/6 vertices, named, from 5af2854:
7
## [1] x1 x2
8
##
9
## [[3]]
10
## + 3/6 vertices, named, from 5af2854:
11
## [1] x1 x2 x3
12
##
13
## [[4]]
14
## + 3/6 vertices, named, from 5af2854:
15
## [1] x1 x2 x4
16
##
17
## [[5]]
18
## + 4/6 vertices, named, from 5af2854:
19
## [1] x1 x2 x3 x6
20
##
21
## [[6]]
22
## + 5/6 vertices, named, from 5af2854:
23
## [1] x1 x2 x3 x6 x5

1
# the distances from 'x1' to the other nodes are:
2
distances(G2, algorithm = "dijkstra", mode = "in")[,1]

1
## x1 x2 x3 x4 x6 x5
2
##  0  1  2  2  3  4