# Como encontrar os menores caminhos de um grafo usando programação dinâmica?

+1 voto
240 visitas
perguntada Mai 18, 2016

## 1 Resposta

+1 voto
respondida Mai 18, 2016 por (5,581 pontos)

A solução apresentada abaixo utiliza a equação de Belman:

$\delta_k (s,v)=\min_{(u,v)\in E} \left(w(u,v)+\delta_{k-1} (s,u) \right),$

onde $\delta_k(s,v)$ é a menor distância do nó $s$ ao nó $v$ usando $k$ arestas.

import numpy as np

def plot_graph(theGraph):
n=len(theGraph)
nxGraph=nx.Graph()
for i in range(n):
for edge in list(theGraph[i]):
e=edge[0]
w=edge[1]
nxGraph[i][e]['weight']=w

labels={}
for i in range(n):
labels[i]=str(i)
pos=nx.spring_layout(nxGraph)
nodeList=range(n)

edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in nxGraph.edges(data=True)])

nx.draw_networkx_edge_labels(nxGraph,pos,edge_labels=edge_weight)
nx.draw_networkx_nodes(nxGraph,pos,node_color='r',node_size=500)
nx.draw_networkx_edges(nxGraph,pos,width=1.0,alpha=0.5,arrows=True)
nx.draw_networkx_labels(nxGraph,pos,labels,font_size=16)
plt.axis('off')
plt.savefig("theGraph.eps")

def shortestPath(theGraph,source):
n=len(theGraph)
delta=float("inf")*np.ones([n,n])
delta[0,source]=0
for k in range(1,n): # step
for v in range(n): # Note
delta[k,v]=delta[k-1,v]
costs= [weights[1] for weights in theGraph[v]]
neighbors=[e[0] for e in theGraph[v]]
for j in range(0,len(theGraph[v])):
if((costs[j]+delta[k-1,neighbors[j]])<delta[k,v]):
delta[k,v]=costs[j]+delta[k-1,neighbors[j]]
return delta

def reconstructShortestPath(theGraph,delta,source,target):
n=len(theGraph)
path=np.empty([n],int)
path[n-1]=target
for k in range(1,n):
neighbors=[e[0] for e in theGraph[path[n-k]]]
costs= [weights[1] for weights in theGraph[path[n-k]]]
minValue=delta[n-k-1,path[n-k]]
path[n-k-1]=path[n-k]
for j in range(0,len(theGraph[path[n-k]])):
if(delta[n-k-1,neighbors[j]]+costs[j]<minValue):
minValue=delta[n-k-1,neighbors[j]]+costs[j]
path[n-k-1]=neighbors[j]
if(path[n-k-1]==source):
break
return path[n-k-1:n]

if __name__ == '__main__':

n=5 #number of nodes

# Structure for outputDegree
theGraph=[set() for i in range(n)]

plot_graph(theGraph)

# However, we need indegree
inTheGraph=[set() for i in range(n)]
for v in range(0,n):
edges=[e[0] for e in theGraph[v]]
weights= [w[1] for w in theGraph[v]]
for j in range(0,len(theGraph[v])):

source=0
delta=shortestPath(inTheGraph,source)
print delta
path=reconstructShortestPath(inTheGraph,delta,source,4)
print path


Para o grafo, encontramos a seguinte output:

# Output

[[  0.  inf  inf  inf  inf]
[  0.   2.  inf   6.  inf]
[  0.   2.   5.   6.  15.]
[  0.   2.   5.   6.  12.]
[  0.   2.   5.   6.  12.]]
[0 1 2 4 4]