# Synopse

Brief function synopse: This function returns the least cost path between two vertices t e s, using Dijkstra algorithm with a modified connectivity function.

Input:
• t - target vertex
• s - root vertex
Output:
• Cost - cost between t and s
• Path - pathcost between t and s
• Vertex - vertex offering the best cost

# Description

Given an adjacency matrix A and a connectivity function assigning a value from root vertex s to target vertex t. The function returns the cost from vertex t to s performing a maximization between vertex cost and path cost.

The functions accepts multiple seeds, in which case, t shall receive the list of multiple seeds and s the target vertex.

# Function Code

``` 1 from numpy import *
2 from iacc_fra import ianeighvert
3
4
6     sizeG=G.shape[0]
7     d = {}
8     previous = {}
9     for v in arange(sizeG):
10         d[v] = float('inf') # infinity
11         previous[v] = None
12     del v
13     d[s] = 0
14     S = []
15
16     Q = list(arange(sizeG))
17
18     def ExtractCheapest(Q):
19         m = None
20         md = None
21         for u in Q:
22             if m is None:
23                 m = u
24                 md = d[u]
25             else:
26                 if d[u] < md:
27                      md = d[u]
28                      m = u
29         Q.remove(m)
30         return m
31
32     while Q:
33         u = ExtractCheapest(Q)
34
35         S.append(u)
36         ngb=ianeighvert(G,u)
37
38         for v in ngb:
39             mxd=max(d[u],G[u,v])
40
41             if mxd < d[v]:
42                 d[v] = mxd
43                 previous[v] = u
44
45     C=[]
46     S=[]
47     CC=[]
48
49     for i in range(len(t)):
50         Sc = []
51         u = t[i]
52         while previous[u] is not None:
53             Sc.insert(0, u)
54             u = previous[u]
55         C.append(d[t[i]])
56         CC.append(len(Sc))
57         S.append(t[i])
58     soma=0.0
59     for j in arange(sizeG):
60         soma=soma+d[j]
61
62     return C,CC,S,soma
```

# Example

## Example 1

Simple graph o illustrate function usage

``` 1 from iadijkstra_fra import *
3
4 graph01 = array([[inf,3,inf,7,inf,inf,inf,inf,inf],[3,inf,2,inf,1,inf,inf,inf,inf],
5 [inf,2,inf,inf,inf,11,inf,inf,inf],[7,inf,inf,inf,9,inf,5,inf,inf],
6 [inf,1,inf,9,inf,4,inf,12,inf],[inf,inf,11,inf,4,inf,inf,inf,10],
7 [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]])
8
10 mmgraphviz(graph, 'Graph with 8 nodes used in classroom')
12 print ("One seed")
13 print ("Sum:")
14 print (r1[3])
16 print ("Two seeds")
17 print ("Sum:")
18 print (r1[3])
19 print ("Cost per path to reach target node 8")
20 print (r1[0])
21 print ("Number of nodes in path")
22 print (r1[1])
23 print ("ID o each node in above lists")
24 print (r1[2])
```
```One seed
Sum:
41.0
Two seeds
Sum:
53.0
Cost per path to reach target node 8
[7.0, 6.0]
Number of nodes in path
[4, 3]
ID o each node in above lists
[0, 3]
```

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