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