# Synopse

Input:
• M Array: Adj. matrix
• seedIndex Array: Seed node
Output:
• costs Array: with the costs considering the seed

# Description

Dijkstra algorithm considering the max function as cost.

Algoritmo 1:

# Function Code

``` 1 from numpy import *
2 from courseIA368Q1S2012.tia_libGraph import *
3
5
6     #Tratando matrizes com Inf
7     matrixCopy = triu(copy(M))
8     matrixCopy[matrixCopy==Inf]=0
9     matrixCopy = nan_to_num(matrixCopy)
10
11     currentNode = seedIndex
12
13     numElements = shape(matrixCopy)[0]
14
15     #Matrix de custo dos nos
16     costs = zeros(numElements)-1
17
19     #visitedNodes = [False for i in range(numElements)]
20     visitedNodes = zeros(numElements)
21
22     #Condicoes iniciais
23     costs[currentNode] = 0
24
25     while(True):
26         #Visitando o nó
27         visitedNodes[currentNode] = True
28
29         #Condição de parada Visitou todos os nós
30         if(sum(visitedNodes)==numElements):
31             break
32
33         neighbours = checkNeighbours(matrixCopy,currentNode,isDigraph=False)
34
35         for neighbour in neighbours:
36
37             if(visitedNodes[neighbour]==1):
38                 continue
39
40             #Condicao da matriz triangular superior
41             nodeA = min(currentNode,neighbour)
42             nodeB = max(currentNode,neighbour)
43
44             #Soma
45             #possibleNewCost = costs[currentNode] + matrixCopy[nodeA][nodeB]
46
47             #Usando fmax
48             possibleNewCost = max(costs[currentNode],matrixCopy[nodeA][nodeB])
49
50             if((costs[neighbour]==-1)or(costs[neighbour]>=possibleNewCost)):
51                costs[neighbour] = possibleNewCost
52
53         #Definindo o menor custo para o próximo passo que é o mínimo dos custos que NÃO foram visitados
54         nonVisited = where(visitedNodes==0)[0]
55         nonVisitedMajor0 = nonVisited[where(costs[nonVisited]>0)[0]]
56
57         #Condição de parada. Grafo não conectado
58         if(len(nonVisitedMajor0)==0):
59             costs[0] = Inf
60             break
61
62         currentNode = nonVisitedMajor0[argmin(costs[nonVisitedMajor0])]
63
64
65     return costs
```
```/usr/local/lib/python2.6/dist-packages/scikits/__init__.py:1: UserWarning: Module dateutil was already imported from /usr/local/lib/python2.6/dist-packages/matplotlib-1.1.0-py2.6-linux-x86_64.egg/dateutil/__init__.pyc, but /usr/lib/pymodules/python2.6 is being added to sys.path
__import__('pkg_resources').declare_namespace(__name__)
```

# Performance Tests

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