//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :5  (5_6)                   *
//*PROGRAM          :最短路徑                   *
//*CONTENT          :弗洛依德算法               *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 10000    //定義權(quán)值的最大值 
#define MAX_NUM 20 //圖的最大頂點數(shù)
enum BOOL {False,True};
typedef struct
{int arcs[MAX_NUM][MAX_NUM]; //鄰接矩陣
 int vexnum,arcnum;                //圖的當(dāng)前頂點和邊數(shù)
}Graph;
void CreateGraph(Graph &);    //生成圖的鄰接矩陣
void ShortestPath_Floyd(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);
    //用弗洛依德算法求每對頂點之間的最短路徑
void Print_ShortestPath(Graph,BOOL[][MAX_NUM][MAX_NUM],int[][MAX_NUM]);
    //顯示用弗洛依德算法所求得的最短路徑
void Print_OnePath(int,int,int,BOOL[][MAX_NUM][MAX_NUM]);
    //顯示一對頂點之間的最短路徑
void main()
{Graph G;  //采用鄰接矩陣結(jié)構(gòu)的圖
 char j='y';
 int u;
 BOOL P[MAX_NUM][MAX_NUM][MAX_NUM]; //存放每對頂點的最短路徑
 int D[MAX_NUM][MAX_NUM];                 //存放每對頂點的最短路徑的距離
 textbackground(3);  //設(shè)定屏幕顏色
 textcolor(15);
 clrscr();
 //------------------程序解說----------------------------
 printf("本程序?qū)⒀菔纠酶ヂ逡赖滤惴ㄇ髨D的每一對頂點之間的最短路徑。\n");
 printf("首先輸入圖的頂點和弧的數(shù)目。\n例如：3,5\n");
 printf("接著輸入弧(i,j)和其權(quán)值。\n例如：\n1,2,4\n2,1,6\n1,3,11\n3,1,3\n2,3,2\n");
 printf("程序?qū)@示出每對頂點之間的最短路徑值和所經(jīng)過的路徑：\n");
 printf("4  1->2\n6  1->2->3\n5  2->3->1\n2  2->3\n3  3->1\n7  3->1->2\n");
 //------------------------------------------------------
 while(j!='N'&&j!='n')
      {CreateGraph(G);       //生成鄰接矩陣結(jié)構(gòu)的圖
       ShortestPath_Floyd(G,P,D); //利用弗洛依德算法求最短路徑
       Print_ShortestPath(G,P,D); //顯示每對頂點之間的最短路徑
       printf("繼續(xù)執(zhí)行嗎?(Y/N)");
       scanf(" %c",&j);
     }
 printf("程序運行結(jié)束，按任意鍵退出窗口!");
 getch();
}

void CreateGraph(Graph &G)
{//構(gòu)造鄰接矩陣結(jié)構(gòu)的圖G
 int i,j;
 int start,end,weight;
 printf("請輸入頂點和弧的數(shù)目，格式：頂點數(shù)，弧數(shù)\n");
 scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點數(shù)和邊數(shù)
 for(i=1;i<=G.vexnum;i++)
    for(j=1;j<=G.vexnum;j++)
      G.arcs[i][j]=INFINITY; //初始化鄰接矩陣
 printf("請輸入各條弧和其權(quán)值，格式：弧尾，弧頭，權(quán)值：\n");
 for(i=1;i<=G.arcnum;i++)
   {scanf("%d,%d,%d",&start,&end,&weight); //輸入邊的起點和終點及權(quán)值
    G.arcs[start][end]=weight;
   }
}
void ShortestPath_Floyd(Graph G,BOOL P[][MAX_NUM][MAX_NUM],int D[][MAX_NUM])
{//用弗洛依德算法求有向網(wǎng)G的每對頂點v和w之間的最短路徑P[v][w]
 //及其帶權(quán)路徑長度D[v][w],
 //若P[v][w][u]為True,表明u是從v到w當(dāng)前求得最短路徑上的頂點
 int u,v,w,i;
 for(v=1;v<=G.vexnum;v++) //各對頂點之間的初始已知路徑及距離
   for(w=1;w<=G.vexnum;w++)
    {D[v][w]=G.arcs[v][w];
     for(u=1;u<=G.vexnum;u++) P[v][w][u]=False;
     if(D[v][w]<INFINITY)     //從v到w有直接路徑
	{P[v][w][v]=True;P[v][w][w]=True;}
    }
 for(u=1;u<=G.vexnum;u++)
    for(v=1;v<=G.vexnum;v++)
      for(w=1;w<=G.vexnum;w++)
	if(D[v][u]+D[u][w]<D[v][w]&&v!=w) //從v經(jīng)u到w的一條路徑更短
	   {D[v][w]=D[v][u]+D[u][w];
	    for(i=1;i<=G.vexnum;i++)
	       if(P[v][u][i]||P[u][w][i]) P[v][w][i]=True;
	   }
}

void Print_ShortestPath(Graph G,BOOL P[][MAX_NUM][MAX_NUM],int D[][MAX_NUM])
{//顯示每對頂點之間的最短路徑及距離
 int v,w,j;
 printf("最短路徑：\n");
 for(v=1;v<=G.vexnum;v++)
   for(w=1;w<=G.vexnum;w++)
     if(D[v][w]<INFINITY)  //頂點v和w之間有通路
	{printf("%-5d",D[v][w]); //從v到w的最短距離
	 Print_OnePath(v,w,G.vexnum,P); //顯示從v到w的最短路徑
	 printf("\n");
	}
}
void Print_OnePath(int v,int w,int num,BOOL P[][MAX_NUM][MAX_NUM])
{//顯示從v到w的最短路徑
 int i;
 for(i=1;i<=num;i++)
    if(i!=v&&i!=w&&P[v][w][i]==True) break;
 if(i>num) printf("%d->%d",v,w); //說明從v到w不需經(jīng)過其它的頂點
 else {Print_OnePath(v,i,num,P); //否則從v到w需經(jīng)過頂點i，先顯示從v到i的最短路徑
       if(i<10) printf("\b");  //控制顯示格式，消除多余的"->"
       else printf("\b\b");
       Print_OnePath(i,w,num,P); //顯示從i到w的最短路徑
      }
}