IGRAPH IN R : 모서리 속성의 곱을 최대화하는 정점 사이의 경로 찾기

Question

모서리 속성의 곱을 최대화하는 두 개의 정점 사이의 경로를 찾는 방법을 찾아야합니다. 필자의 경우 edge 특성은 연결 확률입니다. 이 전 다음 예에서 정점 1과 4 사이의 최대 확률 경로를 찾으려면 가정하자 :이 예에서

require(igraph)  
G<-graph.data.frame(as.data.frame(cbind(id1=c(1,1,2,3,1,4),id2=c(2,3,4,4,5,5),weight=c(0.5,0.35,0.5,0.9,0.6,0.6))), directed=FALSE) 

plot(G, edge.label=paste(E(G),"=",signif(E(G)$weight, digits=1)), vertex.size=10) 

#weighted shortest path using connection probability 
a<-get.shortest.paths(G,1,4, weights=E(G)$weight, output="epath")[[1]] 
E(G)[a] 
prod(E(G)$weight[a]) 

#weighted shortest path using the inverse of connection probability 
b<-get.shortest.paths(G,1,4, weights=1-E(G)$weight, output="epath")[[1]] 
E(G)[b] 
prod(E(G)$weight[b]) 

를 연결을 극대화 경로는 사실, 정점 5까지의 제품입니다 확률은 0.36 (0.6 * 0.6)과 같습니다. 최단 경로 기능은 속성의 합계를 기준으로 우선 순위를 부여하지만 제품은 그렇지 않습니다. 사실 위의 예에서 확률 또는 확률의 역수를 사용하면 연결 확률이 낮은 두 경로 (0.25 및 0.315)를 제안합니다.

제품을 최대화하는 경로를 찾는 방법이 있습니까? 감사합니다.

Answer 1

가장 긴 경로를 얻으려면 최단 경로 알고리즘을 사용하고 있습니다. 반전 가중치가 필요합니다. 동시에 당신은 합계가 아닌 제품을 최대화하기를 원합니다. 결합 -