iadijkstra_wes() Function

Synopse

This function implements Max-Dijkstra algorithm.

  • distances = iadijkstra_wes(AdjMatrix)

    • Output

      • distances: Distance vector containing the distances of each node.
    • Input

      • AdjMatrix: Weighted Adjacency matrix of the graph. 'Inf' value means unconnected vertices.

Function Pseudocode

Algoritmo 1:

Function Code

 1 from numpy import *
 2 
 3 #apresentando os vizinhos de cada vértice
 4 def GrafoNeighborVertex(A,v):
 5     indice=where(A[:,v]!=float('inf'))
 6     return indice[0]
 7 
 8 
 9 def iadijkstra_wes(MA):
10 
11   MK = ones((len(MA[0])))*0
12 
13 
14   d=[]
15   Q=[]
16   Tam = len(MA[0])
17   for i in range(Tam):
18     d.append([float('inf'),-1,i])
19     Q.append(i)
20 
21   d[0][0]=0
22   d[0][1]=0
23   #enquanto existir um vértice ainda não analisado
24   while Q:
25       #ordenando os vértices de menores custos
26       d.sort(key=lambda x:x[0])
27       i=0
28 
29       TamQ=len(Q)
30       sai=0
31       Cj = set(Q)
32 
33       while not(d[i][2] in Cj):
34         i+=1
35         if i==Tam:
36            sai=1
37            break
38 
39       if sai:
40          break
41 
42       Ve = Q.pop(Q.index(d[i][2]))
43       AH = GrafoNeighborVertex(MA,Ve)
44       d.sort(key=lambda x:x[2])
45       for j in AH:
46         if d[j][2] in Cj:
47            #if d[j][0]==float('inf'):
48            if d[j][0]>d[Ve][0]:
49               if d[j][0]==float('inf'):
50                  d[j][0]=MA[Ve,j]
51                  d[j][1]=Ve
52 
53               #if MA[Ve,j]<d[d[j][1]][0]:
54               if MA[Ve,j]<d[Ve][0]:
55                  d[j][0]=d[Ve][0]
56                  d[j][1]=Ve
57 
58               if MA[Ve,j]<d[j][0] and d[Ve][0]<d[j][0]:
59                  d[j][0]=MA[Ve][j]
60                  d[j][1]=Ve
61 
62   d.pop(0)
63   for i in range(Tam-1):
64      MK[d[i][2]]=d[i][0]
65 
66   return MK

Examples

  • It's a single example of the function's use.
 1 from iadijkstra_wes import iadijkstra_wes
 2 
 3 MA = array([[inf,3,inf,7,inf,inf,inf,inf,inf],
 4             [3,inf,8,inf,1,inf,inf,inf,inf],
 5             [inf,8,inf,inf,inf,11,inf,inf,inf],
 6             [7,inf,inf,inf,9,inf,5,inf,inf],
 7             [inf,1,inf,9,inf,4,inf,12,inf],
 8             [inf,inf,11,inf,4,inf,inf,inf,10],
 9             [inf,inf,inf,5,inf,inf,inf,2,inf],
10             [inf,inf,inf,inf,12,inf,2,inf,6],
11             [inf,inf,inf,inf,inf,10,inf,6,inf]])
12 
13 
14 print sum(iadijkstra_wes(MA))
46.0

Performance Test

These tests are imported from Optimum Path Test Page. Example using four different graphs. The results and the processing time are diplayed in a Table.

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

Autor Funcao Simple Test Graph   Complete(v =50)   Complete(v =100)   3 connected components  
Wesley iadijkstra_wes 0.487 ms 41.0 9.811 ms 476.028758628 33.718 ms 394.654708216 0.562 ms inf

References

[Feof2009]Paulo Feofiloff. Algoritmos para Grafos em C via Sedgewick. IME-USP. http://www.ime.usp.br/~pf/algoritmos_para_grafos

See also

  • iaprim - Prim's algorithm implementatoion for finding MSTs

Contributions

  • Wesley Souza, 1o semestre de 2012.