# Synopse

iadijkstra_fer - Implements the Dijkstra Algorithm with one seed

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

# Performance Tests

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