#include "MGraph.h" 
Status GreateGraph(MGraph* G)
{//采用鄰接矩陣表示法，構造圖G 
  scanf("%d",&G->kind); 
  switch(G->kind)
  {
    case DG: return GreateDG(G); //構造有向圖 G
    case DN: return GreateDN(G); //構造有向網 G
    case UDG: return GreateUDG(G) ; //構造無向圖 G
    case UDN: return GreateUDN(G); //構造無向網 G
    default : return ERROR ;           
  }  
  return OK ; 
}  

Status GreateUDN(MGraph* G)
{//采用鄰接矩陣表示法，構造無向網G
  int i=0;
  int j=0; 
  int k=0; 
  scanf("%d %d",&G->vexnum,&G->arcnum);  
  // 構造頂點向量  
  for(i=0;i<G->vexnum;i++)
  {
    scanf("%d",&G->vexs[i]);                        
  }  
  //構造鄰接矩陣 
  for(i=0;i<G->vexnum;i++)
   for(j=0;j<G->vexnum;j++)
   {        
    scanf("%d",&G->arcs[i][j]);      
     if(G->arcs[i][j]<0)   
     G->arcs[i][j] = INT_MAX ;            
   }   
   return OK;    
}  

Status GreateUDG(MGraph* G)
{//采用鄰接矩陣表示法，構造無向圖G
 GreateUDN(G); 
 return OK;      
} 
Status GreateDG(MGraph* G)
{//采用鄰接矩陣表示法，構造有向圖G
   GreateUDN(G); 
   return OK;      
}

Status GreateDN(MGraph* G)
{//采用鄰接矩陣表示法，構造有向網G
 GreateUDN(G);
  return OK;     
} 

int MGraphMGraphLocalVex(MGraph* G,int v)
{ //返回圖中頂點的位置 ,沒找到返回-1 
  int i; 
  for(i=0;i<G->vexnum;i++)
  {
    if(G->vexs[i]==v)
    return i;                        
  }    
 return -1;   
} 

void ShortestPath_DIJ(MGraph* G,int v0,int** P,int* D)
{//用DiJstra算法求有向網G的v0頂點到其余頂點v的最短路徑P[v]及其帶權長度D[v]
//若p[v][w]為1，則w是從v0到v當前求得最短路徑上的頂點
//final[v]為1，當且僅當v屬于S，即已經求得從v0到v的最短路徑 
 int v,w,min,k,i;  
 int* final=(int*) malloc(G->vexnum*sizeof(int)) ; 
 for(v=0;v<G->vexnum;++v)
 {
   final[v]= 0; D[v] =G->arcs[v0][v]; 
   for(w=0;w < G->vexnum ;++w)
   P[v][w] = 0 ;//設空路徑
   if(D[v]<INT_MAX)
   {
     P[v][v0] =1; P[v][v] =1; //與v0與v有弧相連接                
   }                       
 } 
  D[v0] =0; final[v0] =1; //初始化，v0屬于S集 
  //開始主循環，每次求得v0到某個v頂點的最短路徑，并加v到S集 
   for(i=1;i<G->vexnum;++i)
   {
     min= INT_MAX;// 當前所知離v0頂點最近的距離 
     for(w=0;w<G->vexnum;++w)
      if(!final[w]&&D[w]<min)
      {
        min=D[w]; v=w;   //w頂點離v0 更近                   
      } 
      final[v]=1; // 離v0最近的 v加入S集 
     
      for(w=0;w<G->vexnum;++w)
      {
        if(!final[w]&&min+G->arcs[v][w]<D[w])
        {
          D[w] = min+G->arcs[v][w];
          for(k=0;k<G->vexnum;k++)  //p[w] =p[v] +[w] 
          P[w][k] = P[v][k] ;
          P[w][w] =1;                                      
        }                        
      }                
   } 
   free(final); 
} 

void ShortestPath_FLOYD(MGraph* G,int***P,int**D) 
{//用FLOYD算法求有向網G中各頂點v到w之間的最短路徑P[v][w]及
//帶權長度D[v][w]，若P[v][w][u]為1，則u是從v到w當前求得最短路徑上的頂點
  int v,w,u,i; 
  for(v=0;v<G->vexnum;++v)//各對結 點 之間初始已知路徑 及距離  
   for(w=0;w<G->vexnum;++w)
    {
      D[v][w] =G->arcs[v][w] ;
      for(u=0;u<G->vexnum;++u)
       P[v][w][u]=0; 
       if(D[v][w] < INT_MAX)
       {
         P[v][w][v]=1 ;  P[v][w][w]=1 ;        
       }                      
    } 

  for(u=0;u<G->vexnum;++u)
   for(v=0;v<G->vexnum;++v) 
     for(w=0;w<G->vexnum;++w)    
       if(D[v][u]+D[u][w]<D[v][w])
       {
          D[v][w] = D[v][u]+D[u][w] ;
          for(i=0;i<G->vexnum;i++)
          P[v][w][i]=P[v][u][i]||P[u][w][i] ;                     
       }                             
}