图的单源最短路径就是指，指定有向图的一个顶点，然后求得该顶点到达其它顶点的最短路；

 

算法描述：

 

void Dijkstra(C)

/*对给定的有向图，求从原点1到其余每个顶点的最短路径长*/

{

S ={1};/*1为源点*/

for(i =2 ;i <= n;i++)

{

　　D[i] = C[i][j];

}

for(i =1; i<=n-1;i++)

{

　　从V-S中选择一个w(顶点),使得D[w]的值最小;

　　把w加入S;

　　for(V-S中的每一个顶点v)

　　{

　　　　D[v] = min(D[v],D[w] +C[w][r]);

　　}

}

}

 

算法还是比较简单的；接下来实现：

1 #include 
     
         2 using namespace std;   3   4 //定义集合类：   5 class S   6 {
     7     int* s;   8     int num;   9     int now;  10 public:  11     //初始化集合：  12     S(int n){
    13         num = n;  14         s = new int[num];  15         now = 0;  16     }  17     //添加元素到集合：  18     int addElementype(int a)  19     {
    20         if(now < num)  21         {     22             if(isExist(a) == 0)  23             {
    24                 s[now] = a;  25                 now++;  26                 return 0;  27             }  28             else  29                 return -1;  30         }  31         else  32             return 1;  33          34     }  35     //判断元素是否在集合中：  36     int isExist(int temp)  37     {
    38         int flag =0;  39         for(int i =0 ;i
      
       < number; i++)  75     {
    76         C[i] = new int[number];  77     }  78     for(int i =0 ;i
       
        number-1)  94         {
    95             cout<<"No that point!"<
        
          a[i] ) 149         {
   150             temp  = i; 151         } 152     } 153     return temp; 154 } 155 156 int Min(int a,int b) 157 {
   158     if(a>b) 159         return b; 160     else 161         return a; 162 }
        
       
      
     

程序很简单，一个小时就可以写出来；只要是算法思想没见过，就贴出来了。