Function iadijkstra_fer

Synopse

iadijkstra_fer - Implements the Dijkstra Algorithm with one seed

  • T = iadijkstra_fer(M, s)
    • Output
      • T: array. Array with the cost of the minimum path from each vertice to the seed.
    • Input
      • M: ndarray, 2D, square. Weighted graph matrix.
      • s: integer. Index of the seed vertice

Description

Function that implements the Dijkstra Algorithm (using maximum distance, instead of sum), considering just one seed.

This function returns the cost of the minimum path of each vertice to the seed.

Function Code

 1 from numpy import *
 2 
 3 def iadijkstra_fer(M, s):
 4     n = M.shape[1]
 5 
 6     # vetor de custos
 7     # com marcação para saber se o vértice ja tem o custo minimo calculado
 8     C = zeros((2,n))
 9     C[0,:] = C[1,:]+Inf
10     C[0,s] = 0  # custo da semente é zero
11 
12     t = s
13     while(C[1,t]!=Inf):
14         aux = C[0,t]   # armazena o custo do caminho ate esse vertice
15         C[1,t] = Inf   # marca como vértice com custo ja calculado
16 
17         K = maximum(M[t,:], (ones((1,n))*C[0,t])+C[1,:])    # seleção da aresta de maior custo no caminho
18         C[0,:] = minimum(K,C[0,:])    # seleção do caminho com menor custo
19         C[0,t] = aux
20 
21         t = argmin(C[0,:]+C[1,:])  # escolha dos proximo vertice, aquele com caminho minimo ja calculado
22 
23     return C[0,:]

Example

 1 from numpy import *
 2 import courseIA368Q1S2012.fer_lib as lib
 3 from iadijkstra_fer import iadijkstra_fer
 4 
 5 M = array(([[Inf, 2, 3, 1, Inf],
 6           [2, Inf, 2, 5, 3],
 7           [3, 2, Inf, Inf, 2],
 8           [1, 5, Inf, Inf, 1],
 9           [Inf, 3, 2, 1, Inf]]))
10 
11 str = lib.drawGraph(M, False, True)
12 mmgraphviz(str, title='Grafo 1')
13 
14 print "Graph1"
15 for i in range(5):
16     print "Seed ", i, iadijkstra_fer(M, i)
Graph1
Seed  0 [ 0.  2.  2.  1.  1.]
Seed  1 [ 2.  0.  2.  2.  2.]
Seed  2 [ 2.  2.  0.  2.  2.]
Seed  3 [ 1.  2.  2.  0.  1.]
Seed  4 [ 1.  2.  2.  1.  0.]
/media/_xsb/iaOPF/iadijkstra_fer/GRVIZ45604_001.png

Grafo 1

Performance Tests

This function is tested by running the tests defined at the page Optimum Path Test.

gravando arquivo: /home/rubens/www/media/Attachments/iaOPF/iadijkstra_fer/testperf.pkl

Autor Funcao Simple Test Graph   Complete(v =50)   Complete(v =100)   3 connected components  
Fernanda iadijkstra_fer 0.576 ms 41.0 2.664 ms 476.028758628 5.59 ms 394.654708216 0.533 ms inf

Contributions

  • Fernanda Brandão Silva, 1o semestre de 2012.