Mike Simmons wrote:
Adam Ocean wrote:I do not understand what is meant with you multiplication
Basically, when you're looking for ways to travel from i to j, and you find a new point k where it's shorter to travel from i to k and then k to j, in that case you need to update the count of ways to travel that route. If there are X equally-short ways to travel from i to k, and there are Y equally short ways to travel from k to j, then there are X * Y ways to travel from i to j by going through k.
Simpler explanation, if you have 3 different routes to go from Los Angeles to Chicago, and 2 different ways to go from Chicago to New York, then you have 2 * 3 = 6 different ways to go from Los Angeles to New York via Chicago.
I think there are some additional changes needed whenever you find a route through k that is equal in distance to the previous best route from i to j:
So whenever you find a better distance than the previous best distance, you ignore the old count and calculate a new one. but when you find the same distance as the previous best distance, you add to the existing count.
Thank you, I did understand your explanation. I have only one problem in my implementation, it calculates the 'doubled' centrality betweenness. Let s,v,t be nodes in my program. The betwenness centrality is defined as the sum of the amount of shortest paths from s to t which include v devided with the amout of shortest paths from s to t.(s,t and v are not equal) In order to get the amount of shortest path from I am using following lemma:
Lemma: v is contained in a shortest path from s to t if:
d(s,t) = d(s,v)+ d(v,t)
d(s,t) denotes the distance from s to t
From this lemma it can be concluded that:
amount of shortest paths from s to t which include v = 0, if d(s,t) < d(s,v) + d(v,t) case
else amount of shortest paths from s to t which include v = count[s][v]* count[v][t], else case
In order to get the centrality betweenness of a node v, I iterate over each node s,t and sum up if s,v and t are not equal.
My problem is that my algorithm returns the 'doubled' centrality betweenness. I am possible to divide it simply by 2, but I want to understand why ?