#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;   }