luid<- "samza595 and rabsh696"
name<- "saman zahid & rabnawaz jansher"
#' @title Dijkstra Algorithm
#' @name dijkstra
#' @param wiki_graph Data Frame of Graph
#' @param init_node Numeric Scalar Input
#' @return return a vector with number represent with the shortest path between nodes with inital node in graph.
#' @description dijkstra algo to find the shortest path from inital node to all other node in input graph
#' @references \url{https://en.wikipedia.org/wiki/Dijkstra\%27s_algorithm}
#' @export
dijkstra<- function(wiki_graph, init_node)
{
col_name<- c("v1","v2","w")
nodes <- as.numeric(unlist(unique(wiki_graph[1]))) #find a nodes from data frame
if( !is.data.frame(wiki_graph) || !(is.numeric(init_node)) ||
length(init_node) != 1 || !(is.element(init_node,nodes)) ||
!any((col_name %in% colnames(wiki_graph)))
)
{
stop()
}
nodes_length <- length(nodes) #get nodes array length
matrix_wiki_graph <- matrix(c(Inf), nrow = nodes_length, ncol = nodes_length ) # create a martix of rows and column on nodes length
for(y in 1:length(wiki_graph[,1])) # convert data frame to matrix
{
matrix_wiki_graph[wiki_graph[y,1],wiki_graph[y,2]]<- wiki_graph[y,3] #setting a value in Martix with weight
}
unvisted_nodes <- rep(FALSE,nodes_length) #set unvisted nodes to false be default
v_result <- rep(Inf, nodes_length) #initlize output vector with INfinity
v_result[which(nodes == init_node)] <- 0 # set a init mode distance
iterator<- 1 #iterator variable for node counts
while(iterator < nodes_length)
{
min <- Inf
for(i in 1:length(nodes)) # get minimum distance node
{
if(unvisted_nodes[i] == FALSE && v_result[i] <= min)
{
min = v_result[i]
min_index = i;
}
}
u <- min_index # set miniumu index
unvisted_nodes[u]<- TRUE #change the status of unvisited node to visted by setting True
for(y in 1:length(nodes)) #find the neighbouring Nodes
{
if (!unvisted_nodes[y] && matrix_wiki_graph[u,y] &&
v_result[u] != Inf && ( (v_result[u]+ matrix_wiki_graph[u,y] < v_result[y] )) )
{
v_result[y] = v_result[u] + matrix_wiki_graph[u,y];
}
}
iterator <- iterator + 1
}#end of whiel loop
v_result
return (c(v_result))
}
#' @title wiki_graph
#' @name wiki_graph
#' @description wiki_graph
#' \itemize{
#' \item v1 numeric vector
#' \item v2 numeric vector
#' \item w numeric vector
#' }
#' @references \url{https://en.wikipedia.org/wiki/Graph}
## wiki_graph
wiki_graph <- data.frame(v1=c(1,1,1,2,2,2,3,3,3,3,4,4,4,5,5,6,6,6), v2=c(2,3,6,1,3,4,1,2,4,6,2,3,5,4,6,1,3,5),w=c(7,9,14,7,10,15,9,10,11,2,15,11,6,6,9,14,2,9))
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.