# Exercício 7 - Algoritmo de Dijkstra para uma semente

• O algoritmo aqui desenvolvido foi baseado na maneira classica do algoritmo proposto por Dijkstra, simplesmente alterando a operação de soma pela operação de máximo.
``` 1 import wen_lib as w
2 import random
3
4 g = array([[inf,  10,   5, inf, inf, inf],
5            [ 10, inf,   8,   9,   7, inf],
6            [  5,   8, inf, inf,   9,  11],
7            [inf,   9, inf, inf,  10,   5],
8            [inf,   7,   9,  10, inf,   6],
9            [inf, inf,  11,   5,   6, inf]
10           ])
11
12 print g
13
```
```[[ Inf  10.   5.  Inf  Inf  Inf]
[ 10.  Inf   8.   9.   7.  Inf]
[  5.   8.  Inf  Inf   9.  11.]
[ Inf   9.  Inf  Inf  10.   5.]
[ Inf   7.   9.  10.  Inf   6.]
[ Inf  Inf  11.   5.   6.  Inf]]
```

Segue o exemplo do algoritmo:

``` 1 #====================================================================
2 def giDjkMax(sorce,graph):
3
4     vertices = arange(g.shape[0])
5     path_max = ones(g.shape[0]) * inf
6
7     path_max[sorce] = 0
8
9     while(any(vertices>0)):
10         id = (vertices>-1).nonzero()
11         vert_id = where(path_max[id] == path_max[id].min(),id,-1)
12         q = vert_id[vert_id>-1][0]
13         vertices[q] = -1
14
15         path = maximum(ones(g.shape[0]) * path_max[q], graph[q,:])
16         path_max = minimum(path_max,path)
17
18     return path_max
19 #====================================================================
20
21 djk = zeros(g.shape)
22
23 for sorce in arange(g.shape[0]):
24     djk[sorce,:] = giDjkMax(sorce,g)
25
26 print 'Grafo: \n',g
27 print 'Matriz de Distancia: \n',djk
```
```Grafo:
[[ Inf  10.   5.  Inf  Inf  Inf]
[ 10.  Inf   8.   9.   7.  Inf]
[  5.   8.  Inf  Inf   9.  11.]
[ Inf   9.  Inf  Inf  10.   5.]
[ Inf   7.   9.  10.  Inf   6.]
[ Inf  Inf  11.   5.   6.  Inf]]
Matriz de Distancia:
[[ 0.  8.  5.  8.  8.  8.]
[ 8.  0.  8.  7.  7.  7.]
[ 5.  8.  0.  8.  8.  8.]
[ 8.  7.  8.  0.  6.  5.]
[ 8.  7.  8.  6.  0.  6.]
[ 8.  7.  8.  5.  6.  0.]]
```