15.c

来自「OSPF是一种路由选择协议。路由选择算法和路由选择协议在概念上是不同的。网络上的」· C语言 代码 · 共 67 行

#include<iostream.h>
#include<ctype.h>
#include<stdlib.h>
#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<<请输入有向图的顶点个数: "<<end1;
    int NumVertices,temp,v;
    cin>>NumVertices;
    Graph*gSP = new Graph(NumVertices);
    cout<<"请输入源点:\n";
    cin>>v;
coot<< "已生产数组Edge[NumVertices][NumVertices],请输入矩阵各元素的值,"<<end1
        << "正无穷用-1或其他数字字符表示:"<<end1;
    for(int i = 0; i < NumVertices; i++ ){
       cin>>temp;
       if(temp ==-1)
            gSP->Edge[i*NumVertices+j] = MAXINT;
       else
            gSP->Edge[i*NumVertices+j] = temp;
       }
   }
   gSP->ShortestPath(NumVertices,v);
}