# Synopse

This function implements Max-Dijkstra algorithm.

• Output

• dist: Distance vector containing the distances of each node with respect to the seed.
• Input

• graph: Weighted Adjacency matrix of the graph. 'Inf' value means unconnected vertices.
• seed: Seed node that will be used as reference to calculate the distances from the other nodes in the graph.

# Description

This function implements the single-source Max-Dijkstra algorithm.

# Function Code

``` 1 from numpy import*
2
3
5
6    dist = ones((2,len(graph[0])))*float('inf') #seta todas as distâncias igual a 'inf'
7    dist[0,seeds] = seeds
8    dist[1,seeds] = 0
9
10    Q = range(len(graph[0])) #vetor dos vértices do grafo
11
12    while(Q):
13
14       x = (dist[1,Q]).argmin()
15       u = Q[x] # seleciona o vértice com menor distância na fila Q
16
17       if dist[1,u] == float('inf'):
18          break
19
20       Q.remove(u) #Retira p índice da fila
21
22       u_neighbors = findNeighbors(graph,u)
23
24       for k in u_neighbors:
25          if k in Q:
26
27             alt = maximum(dist[1,u], graph[u,k])
28
29             if alt < dist[1,k]:
30                dist[1,k] = alt
31                dist[0,k] = dist[0,u]
32
33
34    return dist
35
36 def findNeighbors(graph,i):
37    connected_vertices = where(graph[i,:]!=float('inf'))
38    return connected_vertices[0]
```

# Examples

These examples apply Max-Dijkstra algorithm for a simple graph and also compares its processing time for graphs with different numbers of edges.

## Example 1:

``` 1 from courseIA368Q1S2012.wen_lib import adj2Graph
3
4
5 graph01 = array([[inf,3,inf,7,inf,inf,inf,inf,inf],[3,inf,2,inf,1,inf,inf,inf,inf],
6 [inf,2,inf,inf,inf,11,inf,inf,inf],[7,inf,inf,inf,9,inf,5,inf,inf],
7 [inf,1,inf,9,inf,4,inf,12,inf],[inf,inf,11,inf,4,inf,inf,inf,10],
8 [inf,inf,inf,5,inf,inf,inf,2,inf],[inf,inf,inf,inf,12,inf,2,inf,6],[inf,inf,inf,inf,inf,10,inf,6,inf]])
9
10
11
13 print 'Distances with respect to node 0: \n', dist
14
```
```/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__)
Distances with respect to node 0:
[[ 0.  0.  0.  0.  0.  0.  0.  0.  0.]
[ 0.  3.  3.  7.  3.  4.  7.  7.  7.]]
```

## 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
Roberto iadijkstra_rob 0.81 ms 41.0 42.233 ms 476.028758628 277.023 ms 394.654708216 0.567 ms inf

# References

 [Feof2009] Paulo Feofiloff. Algoritmos para Grafos em C via Sedgewick. IME-USP. http://www.ime.usp.br/~pf/algoritmos_para_grafos