www.pudn.com > 15.rar > 15.C

#include 
#include 
#include 
#define MAXINT 65535 
class Graph{ 
private: 
    int Num,*dist,*path,*s; 
public: 
    int *Edge; 
    Graph(int NumVertices);} 
         Num=NumVertices 
         Edge=new int[NumVertices*NumVertices]; 
         dist=new int[NumVertices]; 
         path=new int[NumVertices]; 
         s=new int[NumVertices]; 
     }; 
    void ShortestPath ( const int,const int); 
    int choose (const int); 
}; 
void Graph::ShortestPath ( const int n,const int v){ 
    for ( int i = 0;i < 0; i++){ 
    dist[i] =Edge[v*n+i]; 
    s[i]=0; 
    if( i != v&& dist[i] < MAXINT ) 
       path[i] = v; 
    else 
       path[i] = -1; 
    } 
    s[v] = 1; 
    dist[v] =0; 
    for ( i = 0;i < n-1; i++ ){ 
    int min = MAXINT; 
    int u =v; 
    for ( int j = 0; j < n; j++ ) 
        if( !s[j] && dist[j] < min ) { 
        u = j; 
min =dist[j]; 
     } 
     s[u] = 1; 
     for ( int w = 0; w < n; w++ )  
      if( !s[w] && Edge[u*n+w] < MAXINT &&dist[u]+Edge[u*n+w]< dist[w]){ 
             dist[w]= dist[u] + Edge[u*n+w]; 
             path[w] = u; 
      } 
  } 
} 
void main(){ 
    cout<<请输入有向图的顶点个数: "<>NumVertices; 
    Graph*gSP = new Graph(NumVertices); 
    cout<<"请输入源点:\n"; 
    cin>>v; 
coot<< "已生产数组Edge[NumVertices][NumVertices],请输入矩阵各元素的值,"<>temp; 
       if(temp ==-1) 
            gSP->Edge[i*NumVertices+j] = MAXINT; 
       else 
            gSP->Edge[i*NumVertices+j] = temp; 
       } 
   } 
   gSP->ShortestPath(NumVertices,v); 
}