I'm not sure if can post this here as the question is not about the actual implementation in C but more of the theory necessary to implement the algorithm.
I have a undirected weighted graph. I need to find the Betweenness centrality on a node x. For this I would need to find all the shortest paths from a node z to y and then the shortest paths from z to y with x in it.
Any suggestions on which Algorithm to do this in the best possible time complexity ? I have to do this in C.
Well I guess you start here -> Dijkstra's algorithm - Wikipedia
But the shortest path with x might in fact be the longest path.
So do you need to find all possible paths, and then sort them by length?
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
Have to find the shortest ones only. If the shortest path that goes through x is larger than the shortest path available without passing through x, then the value should be 0.Originally Posted by Salem
So the answer is simple then.
You find the shortest path.
If that path contains x, then you do what you need to do.
If it doesn't contain x, then your answer is by your definitions, zero.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
If I'm correct, I can also use Floyd's algorithm cause it finds all the shortest distances and paths from all nodes to every other nodes. But supposing there are multiple shortest paths of same size from to x to z, then I would have to modify the original algorithm to find these, correct ? Or is the complexity to high and Dijkstra be the best possibility to solve this problem ?
It looks like you know what to do - good luck.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
