#include "iostream.h"
#include "assert.h"
   const int NumVertices = 6;				//圖中最大頂點個數
   const int MAXINT=32767;
   class Graph {						//圖的類定義
   private:
      int n;
      int Edge[NumVertices][NumVertices];		//圖的鄰接矩陣
      int dist[NumVertices];					//存放從頂點0到其它各頂點的最短路徑長度
      int path[NumVertices];					//存放在最短路徑上該頂點的前一頂點的頂點號
      int S[NumVertices];					    //已求得的在最短路徑上的頂點的頂點號
   public:
      void ShortestPath ( const int );
      int choose ( const int );
      void BestPath(ostream& os);
      void BellmanFord ( const int v );
      friend istream& operator >>(istream& strm, Graph & g);
   };

   void Graph::ShortestPath ( const int v ) {
   //G是一個具有n個頂點的帶權有向圖, 各邊上的權值由Edge[i][j]給出。本算法建立起一個數組: dist[j], 0 < j < n,
   //是當前求到的從頂點v到頂點j的最短路徑長度, 同時用數組path[j],	0 < j < n, 存放求到的最短路徑。
      assert(((v<n) &&(v>=0)));
      for ( int i=0; i<n; i++) {				// dist和path數組初始化
	    dist[i] = Edge[v][i];					//鄰接矩陣第v行元素復制到dist中
	    S[i] = 0;						//已求出最短路徑的頂點集合初始化
	    if ( i != v && dist[i] < MAXINT ) path[i] = v;
	    else path[i] = -1;					//路徑存放數組初始化
      }
      S[v] = 1;  dist[v] = 0;					//頂點v加入頂點集合
      for ( i=0; i<n-1; i++ ) {				//從頂點v確定n-1條路徑
	    int min = MAXINT;
	    int u = v;
	    for ( int j=0; j<n; j++ )				//選擇當前不在集合S中具有最短路徑的頂點u
	      if ( !S[j] && dist[j] < min ) { u = j;  min = dist[j]; }
	    S[u] = 1;						//將頂點u加入集合S, 表示它已在最短路徑上
	    for ( int w=0; w<n; w++ )			//修改
	      if ( !S[w] && Edge[u][w] < MAXINT && dist[u] + Edge[u][w] < dist[w] ) {
		    dist[w] = dist[u] + Edge[u][w];  path[w] = u;
	      }
      }
   }
   istream& operator >>(istream& strm, Graph & g)
   {
	strm>>g.n;
	    for (int i=0;i<g.n;i++)
	    {
		    for (int j=0;j<g.n;j++)
		    {
			    strm>> (g.Edge[i][j]);
		    }

	    }
	    return strm;

   }
   void Graph::BestPath(ostream& os)
   {
	   os<<"shortest dist:";
	   for (int i=0;i<n;i++)
	   {
	      os<<dist[i]<<" ";
	   }
	   os<<endl;
	   os<<"shortest path:";
	   for ( i=0;i<n;i++)
	   {
	      os<<path[i]<<" ";
	   }
	   os<<endl;
   }