Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

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

0 votos
44 visitas
perguntada Mai 18, 2016 em Ciência da Computação por danielcajueiro (5,251 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Mai 18, 2016 por danielcajueiro (5,251 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.add_edge(i,e)
            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)]
     theGraph[0].add((1,2.0))
    theGraph[0].add((3,6.0))
    theGraph[1].add((0,2.0))
    theGraph[1].add((2,3.0))
    theGraph[1].add((3,8.0))
    theGraph[1].add((4,20.0))
    theGraph[2].add((1,3.0))
    theGraph[2].add((4,7.0))
    theGraph[3].add((0,6.0))
    theGraph[3].add((1,8.0))
    theGraph[3].add((4,9.0))
    theGraph[4].add((1,20.0))
    theGraph[4].add((2,7.0))
    theGraph[4].add((3,9.0))

    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])):
            inTheGraph[edges[j]].add((v,weights[j]))

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

Para o grafo, encontramos a seguinte output:

shortest path dynamic programming.

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