?? 最短路徑算法.txt
字號:
/*GIS 環境下的最短路徑規劃算法,此處最短路理解為路徑長度最小的路徑*/
/*設計人：劉繼忠*/
/*學號：2002374117*/
/*建議用C++編譯程序編譯,若用TURBOC 2.0可能會造成源程序的排版混亂*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE -1
#define MAXSIZE 20 /*處理圖的最大結點數*/
#define INFINITY 30000 /*允許的節點間的權值的最大值*/
#define ERROR 0
#define SUCCEED 1
typedef struct
{
int vexs[MAXSIZE]; /*存放圖的各頂點數據信息*/
int arcs[MAXSIZE][MAXSIZE]; /*定義鄰接矩陣*/
int vexnum;
int arcnum; /*vexnum為圖的頂點數，arcnum為圖的邊的條數*/
}MGraph;
void Welcome() /*程序初始化界面，介紹程序的功能、特點及相關提示*/
{
textmode(C80);
clrscr();
textcolor(13);
cprintf("\nWelcome to shortest path searching system.\r\n\n\n");
textcolor(10);
textbackground(1);
cprintf(" Instructions \r\n");
textbackground(0);
textcolor(11);
cprintf("Function: \r\n 1. Personal travelling route choosing.\r\n 2. Assistan helper in city's traffic design.\r\n 3. Shortes path choose in the comlicated traffic net of the city.\r\n");
cprintf("\nCharacteristic:\r\n It is convient,you could set vital point you must travel,and the\r\n point you must avoid.\r\n");
cprintf("\nPrompt:\r\n If the condition is too secret ,maybe there will have no path available.\r\n") ;
cprintf("\r\nDesigner: Liu jizhong.\r\nComplate-data: 2004. 3. 21\r\n");
cprintf("CopyRight: Shared program,welcome to improve it.");
textcolor(15+128);
cprintf("\r\n\nPress anykey to enter the program...");
getch();
}
void CreatGraph(MGraph *G,char buf[]) /*把圖用鄰接矩陣的形式表示*/
{
int i,j,k,count; /*i,j為循環控制變量,count為計數變量*/
int x,y,ERROR_x; /*x,y為相應的屏幕控制輔助變量*/
int dist; /*dist為相應的邊的權值*/
int temp; /*temp為零時性中間變量*/
int flag,flag1,flag2; /*flag1flag2為標志位變量*/
textmode(C80);
clrscr();
do{
textcolor(3);
clrscr();
textcolor(4);
textbackground(10);
cprintf("Gather information about the graph:\r\n\n");
textbackground(0);
textcolor(15);
cprintf("Customize codes for the vexs(end up by -1):"); /*為各結點自定義編號*/
flag=1;
G->vexnum=0;
i=0;
while(1) /*循環控制當輸入的自定義的結點有重復時，自動撤銷輸入的該組結點，給出出錯提示信息，并要求重新輸入*/
{
scanf("%d",&temp);
if(temp==-1)
break;
G->vexs[i++]=temp;
G->vexnum++;
for(j=0;j<G->vexnum-1&&G->vexnum>=2;j++)
if(temp==G->vexs[j])
flag=0;
}
if(flag==0)
{
textcolor(5);
cprintf("ERROR: repetitious code!\r\nPlease check and input again.\r\n");
getch();
}
}while(!flag);
if(G->vexnum<=1) /*當用戶自定義的結點數小于2時，給出出錯提示信息，并退出程序*/
{
textcolor(4);
cprintf("\r\n\nERROE:the ammount of the node is less than two,the program will terminate!\r\nPress anykey to exit...");
getch();
exit(0);
}
for(i=0;i<G->vexnum;i++) /*初始化鄰接矩陣*/
{
for(j=0;j<G->vexnum;j++)
G->arcs[G->vexs[i]][G->vexs[j]]=INFINITY;
}
G->arcnum=0;
count=0;
textcolor(9);
clrscr();
textbackground(10);
textcolor(4);
cprintf("Gather information about the graph:\r\n\n");
textcolor(15);
textbackground(0);
cprintf("The code you customized:");
textcolor(3);
for(i=0;i<G->vexnum;i++)
cprintf("%d ",G->vexs[i]);
textcolor(15);
cprintf("\r\n\nInput the arcs's vexs and powers(end up by evaluate -1 to jump-off point):\r\n\n"); /*錄入有向圖的數據信息，各邊的起點、終點和邊上的權值*/
textcolor(5);
cprintf("serial number jump-off point end-point power\r\n");
while(1)
{
while(1)
{
flag1=flag2=0; /*用來記錄輸入各邊的起點和終點的合法性*/
textcolor(11);
if(count<10)
cprintf(" %d ",count++);
else
cprintf(" %d ",count++);
x=wherex();
scanf("%d",&i);
if(i==-1) /*用來控制結束信息的輸入*/
break;
gotoxy(x+24, wherey()-1);
x=wherex();
scanf("%d",&j);
gotoxy(x+17,wherey()-1);
scanf("%d",&dist);
ERROR_x=wherey()-1;
for(k=0;k<G->vexnum;k++)
{
if(i==G->vexs[k])
flag1=1;
if(j==G->vexs[k])
flag2=1;
}
if(flag1&&flag2&&dist<INFINITY&&i!=j) /*當各邊的信息合法時接受該組數據信息*/
break;
else
{
textcolor(4);
if(dist>=INFINITY) /*當輸入邊的權值大于程序允許的范圍時*/
cprintf(" ERROR:The power of the arcs is out of range!\r\n");
else
if(i==j) /*當圖中存在環時*/
cprintf(" ERROE:arc from ome point to itselt is Illegal.\r\n");
else /*當輸入的邊的起點或終點的編號不為用戶剛定義的結點編號時*/
cprintf(" ERROR:The code of the vex is illegal!\r\n");
}
textcolor(10);
cprintf(" Please check the data,then input again."); /*要求用戶檢查數據并重新輸入*/
textcolor(9);
getch();
while(wherey()!=ERROR_x-1)
{
gotoxy(1,wherey());
clreol();
gotoxy(1,wherey()-1);
}
gotoxy(1,wherey()+1);
count--;
}
if(i!=-1)
{
G->arcs[i][j]=dist; /*將合法的結點信息賦入鄰接矩陣中*/
G->arcnum++;
}
else
break;
}
gettext(1,1,80,23,buf); /*將輸入結點的相關信息存入內存的buf中，以便以后查看各結點的信息*/
}
int ShortestPath(MGraph *G,int jump,int end,int avoid[],int P[MAXSIZE][MAXSIZE],int *pSHDist,int ShPath[]) /*根據用戶給出的起點、終點、必經結點、避開結點進行分段查找*/
{
int i,j,k,m,w; /*均為循環控制變量*/
int v,min;
int Dist[MAXSIZE]; /*記錄各結點的當前找到的最短路徑的長度*/
int final[MAXSIZE]; /*final[]為記錄已找最短路徑的結點*/
for(i=0;i<(*G).vexnum;i++) /*將用來記錄用戶給出的起點到圖中其他各點的最短路徑的路徑路的長度的數組Dist[]初始化*/
{
final[G->vexs[i]]=FALSE;
Dist[G->vexs[i]]=(*G).arcs[jump][G->vexs[i]]; /*給Dist數組賦初值*/
for(j=0;j<(*G).vexnum;j++)
P[G->vexs[i]][j]=FALSE;
}
Dist[jump]=0; /*初始化*/
final[jump]=TRUE; /*初始化*/
for(i=0;i<(*G).vexnum;i++) /*P[]][]為記錄用戶給定的起點到其他各點到目前為止找到的最短路徑*/
{
if(((*G).arcs[jump][G->vexs[i]])<INFINITY) /*當從用戶給定的起點到其他的各點間有直接的路徑時才處理*/
{
P[G->vexs[i]][0]=jump;
P[G->vexs[i]][1]=G->vexs[i];
}
}
for(i=0;avoid[i]!=-1;i++)
for(j=0;j<G->vexnum;j++)
if(avoid[i]==G->vexs[j])
final[G->vexs[j]]=TRUE; /*把用戶給定的要避開的結點視為已找到最短路徑的結點，則在找由jump到的end最短路徑時將避開這些結點*/
for(i=1;i<G->vexnum;i++)
{
min=INFINITY;
for(j=0;j<G->vexnum;j++) /*找出尚未求出最短路徑的結點中的的結點的當前的路徑長度的最小值*/
{
if(final[G->vexs[j]]==FALSE&&Dist[G->vexs[j]]<min) /*final[G->vexs[j]]==FALSE，尚未求出到該頂點的最短路徑*/
{
v=G->vexs[j];
min=Dist[G->vexs[j]];
}
}
if(min<INFINITY)
{
final[v]=TRUE;
Dist[v]=min;
}
else /*如果已沒有可用的路徑時*/
break;
if(v==end) /*當結點end的最短路徑已找到時跳出循環*/
break;
for(w=0;w<G->vexnum;w++)
if(final[G->vexs[w]]==FALSE&&(min+(*G).arcs[v][G->vexs[w]]<Dist[G->vexs[w]])&&(*G).arcs[v][G->vexs[w]]<INFINITY) /*符合迪杰斯特拉條件*/
{
Dist[G->vexs[w]]=min+(*G).arcs[v][G->vexs[w]]; /*修改該結點的當前最短路徑的路徑長度值*/
if(v!=G->vexs[w]) /*修改記錄該結點的當前找到的最短路徑所經過結點序列*/
{
for(j=0;P[v][j]!=FALSE&&P[v][j]!=v;j++)
P[G->vexs[w]][j]=P[v][j];
}
if(P[v][j]!=v) /*完善已找到最短路徑的結點所經的結點序列*/
P[v][j]=v;
P[G->vexs[w]][j]=v;
P[G->vexs[w]][++j]=G->vexs[w];
}
}
if(v==end) /*將分段查找到的最短路徑所經的結點存入記錄最終最短路徑的數組中,將分段查找到的最短路徑的權值累加*/
{
for(i=0;ShPath[i]!=-1;i++);
if(i==0)
j=0;
else
j=i-1;
for(m=0;P[v][m]!=-1;j++)
ShPath[j]=P[v][m++];
*pSHDist=*pSHDist+Dist[v];
return SUCCEED;
}
else /*當分段最短路徑查找失敗時*/
{
textcolor(5);
cprintf("\r\nThere is no path available between city[%d] and city[%d]!",jump,end);
textcolor(11);
getch();
return ERROR;
}
}
void Print(int jump,int end,int SHDist,int ShPath[]) /*輸出找到的最短路徑所經的結點和路徑長度*/
{
int i;
textcolor(4);
textbackground(10);
cprintf("The shortest path searching result:\r\n\n");
textbackground(0);
textcolor(11);
printf("The length between city [%d] and city [%d]: %d",jump,end,SHDist);
printf("\nThe shortest path between city [%d] and city [%d]:",jump,end);
printf("%d ",ShPath[0]);
for(i=1;ShPath[i]!=-1;i++)
printf("->%d ",ShPath[i]);
}
main()
{
int i,j,k,n; /*循環控制變量*/
int flag[MAXSIZE],flag1,flag2; /*標志變量*/
int vital_n; /*記錄必經結點的數量*/
int avail[MAXSIZE];
char choice;
int SHDist; /*記錄用戶要求的最短路徑的長度（權值）*/
int jump,end; /*jump記錄用戶給出的起點,end記錄用戶給出的終點*/
int P[MAXSIZE][MAXSIZE]; /*用來記錄各點當前找到的最短路徑所經過的結點*/
int vital[MAXSIZE]; /*記錄用戶給出的必經結點*/
int avoid[MAXSIZE]; /*記錄用戶給出的要避開的結點*/
int ShPath[MAXSIZE]; /*用來存放用戶需要的最短路徑所經的各結點*/
char buf[80*25*2]; /*用來存放在圖的相關信息錄入時的界面信息，以便以后查看各結點的信息*/
MGraph G; /*定義用來存放圖的信息的鄰接矩陣*/
textmode(BW80);
clrscr();
Welcome();
CreatGraph(&G,buf);
textcolor(11);
clrscr();
while(1)
{
for(i=0;i<MAXSIZE;i++) /*初始化用來存放用戶需要的最短路徑所經的各結點的數組*/
ShPath[i]=-1;
for(i=0;i<G.vexnum;i++) /*初始化用來記錄各點當前找到的最短路徑所經過的結點的數組*/
for(j=0;j<MAXSIZE;j++)
P[G.vexs[i]][j]=-1;
for(i=0;i<MAXSIZE;i++)
avail[i]=ERROR;
n=0;
SHDist=0;
textcolor(4);
textbackground(10);
cprintf("Shortest Path searching:\r\n\n");
textbackground(0);
textcolor(11);
printf("The node you customized:"); /*輸出用戶已自定義的各結點的編號以便用戶檢查輸入的合法性*/
for(i=0;i<G.vexnum;i++)
printf("%d ",G.vexs[i]);
while(1)
{
flag1=flag2=0;
printf("\n\nPlease input the jump-off points and the end-point:");
scanf("%d %d",&jump,&end);
for(j=0;j<G.vexnum;j++) /*檢查起點的合法性*/
if(jump==G.vexs[j])
{
flag1=1;
break;
}
for(j=0;j<G.vexnum;j++) /*檢查終點的合法性*/
if(end==G.vexs[j])
{
flag2=1;
break;
}
if(flag1&&flag2)
break;
if(!flag1) /*若起點不合法*/
{
textcolor(5);
cprintf("ERROE:Illegal jump-off point!\r\n");
textcolor(11);
}
if(!flag2) /*若終點不合法*/
{
textcolor(5);
cprintf("ERROR:Illegal end-point!\r\n");
textcolor(11);
}
}
while(1)
{
printf("please input the vital points(end up by -1):");
for(k=0;k<MAXSIZE;k++)
flag[k]=-1;
i=0;
while(1) /*錄入用戶要求必經的結點，并同時檢查其合法性*/
{
scanf("%d",&vital[i++]);
if(vital[i-1]==-1)
break;
for(j=0;j<G.vexnum&&vital[i-1]!=G.vexs[j];j++);
if(j==G.vexnum)
{
textcolor(5);
cprintf("ERROR:Illegal vital point [%d]!\r\n",vital[i-1]);
textcolor(11);
flag[i-1]=0;
}
else
flag[i-1]=1;
}
for(k=0;k<MAXSIZE;k++)
if(flag[k]==0)
break;
if(k==MAXSIZE)
break;
}
vital_n=i-1;
while(1) /*錄入用戶要求避開的結點，并同時檢查其合法性*/
{
printf("please input the avoiding points(end up by -1):");
for(k=0;k<MAXSIZE;k++)
flag[k]=-1;
i=0;
while(1)
{
scanf("%d",&avoid[i++]);
if(avoid[i-1]==-1)
break;
for(j=0;j<G.vexnum&&avoid[i-1]!=G.vexs[j];j++);
if(j==G.vexnum)
{
textcolor(5);
cprintf("ERROR:Illegal avoid point [%d]!\r\n",avoid[i-1]);
textcolor(11);
flag[i-1]=0;
}
else
flag[i-1]=1;
}
for(k=0;k<MAXSIZE;k++)
if(flag[k]==0)
break;
if(k==MAXSIZE)
break;
}
printf("press any key to watch the result...");
getch();
clrscr();
if(vital_n==0) /*當用戶沒用給出要求必經的結點時*/
vital[0]=end;
avail[0]=ShortestPath(&G,jump,vital[0],avoid,P,&SHDist,ShPath);
if(vital_n>=2) /*根據用戶給出的起點、終點、必經結點、避開結點進行分段查找*/
for(i=0;vital[i+1]!=-1;i++)
{
avail[n++]=ShortestPath(&G,vital[i],vital[i+1],avoid,P,&SHDist,ShPath);
/*printf("jump=%d end=%d\n",vital[i],vital[i+1]);*/
}
if(vital_n>=1) /*當用戶只給出了一個必經結點時*/
{
if(vital_n==1)
i=-1;
avail[n]=ShortestPath(&G,vital[i],end,avoid,P,&SHDist,ShPath);
}
for(i=0;i<=n;i++)
if(avail[i]==ERROR)
{
textcolor(4);
cprintf("\r\nPath searching failed!");
textcolor(11);
break;
}
if(i==n+1)
Print(jump,end,SHDist,ShPath);
getch();
clrscr();
while(1) /*詢問用戶是否重新定義起點、終點、必經結點、避開結點并進行再次查找*/
{
textcolor(10);
cprintf("Change the limitataive conditions,then try again?y/n [ ]\b\b");
textcolor(11);
choice=getche();
if(choice=='y'||choice=='Y'||choice=='n'||choice=='N')
break;
gotoxy(0,wherey());
clreol();
}
if(choice=='n'||choice=='N')
break;
clrscr();
printf("The information about the graph.");
puttext(1,3,80,25, buf);
getch();
clrscr();
}
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -