# Synopse

This function implements Max-Dijkstra algorithm.

• Output

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

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

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
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
```
```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.

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