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 
14 mmgraphviz(w.adj2Graph(g))
[[ 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]]
/media/_xsb/courseIA368Q1S2012/gio_7/GRVIZ83215_001.png

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