
June 16th, 2004, 09:26 PM
|
|
Registered User
|
|
Join Date: Jun 2004
Posts: 2
Time spent in forums: < 1 sec
Reputation Power: 0
|
|
|
How to select right subgraph for dijkstra's algorithm
I think we can greatly improve the speed if we can reduce nodes to be processed. I want to find a shortest path from source node A to end node B(single-source and single-end).
So I set up a region what diameter is the linear distance from A to B(I do not know if my expression is right or not), denoted d. Or d can be a bit larger, for instance,d=d+0.5. the region is denoted R.
And I find all nodes in R and thus yields a new graph. we apply the dijkstra's algorithm in this subgraph.
I apply this idea into one of our project and proved to be success. But when I think of writing a paper to be published ,I do not know if it is right or not.
So can any of you give me some advice to improve this algorithm (idea)?
|