[求助]用c编写求最短路径的算法

JAY

这是一个用C++写的，用的是Dijkstra算法，找单源最短路径
[attachment:4929]

1. 
   
2. [img]attachment/2006-1/2006121650435450.gif[/img]
   
3. The adjoining matrix is below:(-1 means no path)
   
4.         1    2    3    4    5
   
5.   ------------------------------
   
6.   1|    0   10    3   20   -1  |
   
7.   2|   -1    0   -1    5   -1  |
   
8.   3|   -1    2    0   -1   15  |
   
9.   4|   -1   -1   -1    0   11  |
   
10.   5|   -1   -1   -1   -1    0  |
    
11.   ------------------------------
    
12. 
    
13. Start from 1:
    
14. Step 1, deal with 1:     0   10    3   20   -1
    
15. Step 2, deal with 3:     0    5    3   20   18
    
16. Step 3, deal with 2:     0    5    3   15   18
    
17. Step 4, deal with 4:     0    5    3   15   18
    
18. Paths:
    
19. Path to 2: 1->3->2
    
20. Path to 3: 1->3
    
21. Path to 4: 1->3->2->4
    
22. Path to 5: 1->3->5
    
23. 
    
24. Start from 2:
    
25. Step 1, deal with 2:    -1    0   -1    5   -1
    
26. Step 2, deal with 4:    -1    0   -1    5   16
    
27. Paths:
    
28. No path to 1
    
29. No path to 3
    
30. Path to 4: 2->4
    
31. Path to 5: 2->4->5
    
32. 
    
33. Start from 3:
    
34. Step 1, deal with 3:    -1    2    0   -1   15
    
35. Step 2, deal with 2:    -1    2    0    7   15
    
36. Step 3, deal with 5:    -1    2    0    7   15
    
37. Paths:
    
38. No path to 1
    
39. Path to 2: 3->2
    
40. Path to 4: 3->2->4
    
41. Path to 5: 3->5
    
42. 
    
43. Start from 4:
    
44. Step 1, deal with 4:    -1   -1   -1    0   11
    
45. Step 2, deal with 5:    -1   -1   -1    0   11
    
46. Paths:
    
47. No path to 1
    
48. No path to 2
    
49. No path to 3
    
50. Path to 5: 4->5
    
51. 
    
52. Start from 5:
    
53. Step 1, deal with 5:    -1   -1   -1   -1    0
    
54. Paths:
    
55. No path to 1
    
56. No path to 2
    
57. No path to 3
    
58. No path to 4

复制代码

[此贴子已经被作者于2006-1-2 17:01:02编辑过]

JAY

原理是一样的，你可以看看Dijkstra.h里面的那个FindPath函数。那个就是寻路的函数。