Dijkstra_Test_2

Introdução

Implementação do Algoritmo Dijkstra, que mede o caminho mais curto. Essa implementação segue as especificações dadas no livro “Algorithm Design” de Jon Kleinberg e Eva Tardos.

Referência: Kleinberg, Jon; Tardos, Eva. “Algorithm Design”. Pearson. 2005. p.137-142.

Passo a passo da implementação

Criação de uma lista de adjacência com dados:

edgesdf <- data.frame(nodea=c(1,2,4,2,1), nodeb=c(1,2,3,4,5))

adjalist <- by(edgesdf, edgesdf$nodea, function(x) x$nodeb)

for(i in as.character(unique(edgesdf$nodea))) {
  cat(i, '->', adjalist[[i]], '\n')
}

## 1 -> 1 5 
## 2 -> 2 4 
## 4 -> 3

myadj <- stack(adjalist) 

Criação do grafo com base na lista de adjacência usando a biblioteca ‘igraph’ em R.

library(igraph)

## 
## Attaching package: 'igraph'

## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum

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

grafo <- graph.data.frame(myadj)

plot(grafo)

Renomear o grafo para aproveitar os códigos já escritos:

graphdj <- grafo

Definição dos parâmetros de input para a função.

Número de nodes:

n = length(graphdj[,1])

Fonte do node:

v = 1

Destino do node:

dest = n

Grafo:

cost = graphdj

Algoritmo Dijkstra

dijkstra = function(n,v,cost,dest){
  # criação de variáveis para guardar os dados
  dest = numeric(n)
  flag = numeric(n)
  prev = numeric(n)
  
  # para cada node da rede, medir a distância começando por v até i 
  for(i in 1:n){
    prev[i] = -1
    dest[i] = cost[v,i]
  }
  # para iniciar o contador que vai marcar o número de passos na rede
  count = 10
  
  # até chegar ao node de destino n
  while(count <= n){
    min = 9
    
    # fazer um loop para cada node
    for(w in 1:n){
      # checar se o caminho é menor do que o que já existe e se for, substituir o caminho mínimo anterior
      if(dest[w] < min && !flag[w]){
        min = dest[w]
        u = w
      }
    }
    # para indicar que a máquina tem que ir para o lugar especificado anteriormente
    flag[u] = 1
    count = count + 1
    
    # Para fazer novamente um loop para cada node, mas lembrando onde já passamos. 
    # Aqui repete o processo de checar o caminho mais curto, atualizar as distâncias e manter um track dos nodes visitados.
    for(w in 1:n){
      if((dest[u]+cost[u,w] < dest[w]) && !flag[w]){
        dest[w]=dest[u]+cost[u,w]
        prev[w]=u
      }
    }
  }
  return(prev)
}

Criação de uma função que retorne o caminho.

save_path = function(f,x){
  path = x
  while(f[x] != -1){
    path = c(path, f[x])
    x = f[x]
    save_path(f,x)
  }
  path = c(path, 1)
  return(path)
}

Rodar o algoritmo Dijkstra no grafo criado.

prev = dijkstra(n,v,cost,dest)
path = save_path(prev,dest)

Resultados:

prev

## [1] -1 -1 -1 -1 -1

path

## [1] 5 1

Comparação com a função já construída da biblioteca ‘igraph’ (R Programming)

dij.paths <- shortest.paths(graphdj, algorithm = "dijkstra")

par(mfrow=c(1,2))
plot(path, main="My Dijkstra Function")
plot(dij.paths, main="Built-in function on 'igraph' library")