兩點間路徑最短演算法

『壹』 最短路徑法如何計算

最短路徑演算法有三種，Floyd，dijkstra，Bellman_Ford。其中，Floyd適合用於計算每兩點間的路徑，dijkstra適合稀疏圖，bellman則適合稠密圖中的已知起點終點，計算最短路徑的問題。時間復雜度，floyd演算法為n立方，dijk為n平方，bellman為n平方，其中n是點數。dijk可用堆維護，時間復雜度可減至nlogn，而bellman可用隊列維護，此方法於1994年被國人提出，命名比較土鱉叫SPFA(shortest path faster algorithm。。。)。至於如何計算，有了名字，搜一下就ok。

『貳』 求有向圖兩個頂點間的最短路徑的方法，用簡單語言或舉例描述。

在交通網路中，常常會提出許多這樣的問題：兩地之間是否有路相通？在有多條通路的情況下，哪一條最近？哪一條花費最少等。交通網路可以用帶權圖表示，圖中頂點表示域鎮，邊表示兩城之間的道路，邊上權值可表示兩城鎮間的距離，交通費用或途中所需的時間等。
以上提出的問題就是帶權圖中求最短路徑的問題，即求兩個頂點間長度最短的路徑。
最短路徑問題的提法很多。在這里僅討論單源最短路徑問題：即已知有向圖(帶權)，我們希望找出從某個源點S∈V到G中其餘各頂點的最短路徑。
例如：下圖(有向圖G14)，假定以v1為源點，則其它各頂點的最短路徑如下表所示：

圖 G14

從有向圖可看出，頂點v1到v4的路徑有3條：(v1,v2,v4)，(v1,v4)，(v1,v3,v2,v4 )，其路徑長度分別為：15,20和10。因此v1到v4的最短路徑為(v1,v3,v2,v4 )。
為了敘述方便，我們把路徑上的開始點稱為源點，路徑的最後一個頂點為終點。
那麼，如何求得給定有向圖的單源最短路徑呢？迪傑斯特拉(Dijkstra)提出按路徑長度遞增產生諸頂點的最短路徑演算法，稱之為迪傑斯特拉演算法。
迪傑斯特拉演算法求最短路徑的實現思想是：設有向圖G=(V,E)，其中，V={1,2,…,n}，cost是表示G的鄰接矩陣，cost[i][j] 表示有向邊<i,j>的權。若不存在有向邊<i,j>，則cost[i][j]的權為無窮大(這里取值為32767)。設S是一個集合，其中的每個元素表示一個頂點，從源點到這些頂點的最短距離已經求出。設頂點v1為源點，集合S的初態只包含頂點v1。數組dist記錄從源點到其他各頂點當前的最短距離，其初值為dist[i]=cost[v1][i]，i=2,…,n。從S之外的頂點集合V-S 中選出一個頂點w，使dist[w]的值最小。於是從源點到達w只通過S 中的頂點，把w加入集合S中調整dist中記錄的從源點到V-S中每個頂點v的距離：從原來的dist[v] 和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v]。重復上述過程，直到S中包含V中其餘頂點的最短路徑。
最終結果是：S記錄了從源點到該頂點存在最短路徑的頂點集合，數組dist記錄了從源點到 V中其餘各頂點之間的最短路徑，path是最短路徑的路徑數組，其中path[i] 表示從源點到頂點i之間的最短路徑的前驅頂點。

『叄』 求圖中任意兩點之間最短路徑有什麼演算法

單源節點到其他任意節點的最短路徑採用Dijkstra演算法，任意兩個節點之間的最短路徑使用Floyd演算法，這兩個演算法有很多地方可以找打。

『肆』 求A到B之間的最短路徑，怎麼獲取

問題：從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑——最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法，另外還有著名的啟發式搜索演算法A*，不過A*准備單獨出一篇，其中Floyd演算法可以求解任意兩點間的最短路徑的長度。任意一個最短路演算法都是基於這樣一個事實：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點到B。
(1) 迪傑斯特拉(Dijkstra)演算法按路徑長度(看下面表格的最後一行，就是next點)遞增次序產生最短路徑。先把V分成兩組：
S：已求出最短路徑的頂點的集合
V-S=T：尚未確定最短路徑的頂點集合
將T中頂點按最短路徑遞增的次序加入到S中，依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權值或是從V0經S中頂點到Vk的路徑權值之和（反證法可證，說實話，真不明白哦）。
(2) 求最短路徑步驟
初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值， 若存在<V0,Vi>，為<V0,Vi>弧上的權值（和SPFA初始化方式不同），若不存在<V0,Vi>，為Inf。
從T中選取一個其距離值為最小的頂點W(貪心體現在此處)，加入S(注意不是直接從S集合中選取，理解這個對於理解vis數組的作用至關重要)，對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值（上面兩個並列for循環，使用最小點更新）。
重復上述步驟，直到S中包含所有頂點，即S=V為止（說明最外層是除起點外的遍歷）。

『伍』 網格中如何求任意兩點間的最短路徑 matlab演算法

function [L,Z]=dijkstra(W,S,T)
%用 Dijkstra 演算法求最短路徑
% 演算法
% 1. 對每個點I指定一個離點S的距離初始值L(I). 在始點S的值為零, 即L(S)=0，其它點的值為Inf.
% 2. 所有的點標記為未走訪的. 置始點S為當前點C.
% 3. 對於當前點C, 考慮它的所有未走訪的相鄰點J, 並更新J的距離值為
% L(J)=min(L(J), L(C)+W(C,J))
% 4. 把當前點C標記為走訪過的點. 走訪過的點C的距離L(C)就是點S到C的最短距離, 而且以後不再檢查走訪過得點了.
% 5. 如果所有的點都是走訪過的點, 完成. 不然, 把未走訪的點中具有最小距離值的點作為下一個當前點C, 轉
N=length(W(:,1));%頂點數
W(find(W==0))=inf;
L=Inf*ones(1,N);
L(S)=0;%L賦初值，在S點為0，其它點為Inf
C=S; %當前點為始點S
Q=1:N;% 未走訪的頂點集
Z=S*ones(1,N);
Z(S)=0;% Z賦初值,因始點 S 無父親點,故把 S 點的Z值改為0
for K=1:N % 更新 L 和 Z 的循環
Q=setdiff(Q,C); %Matlab自帶函數，顯示Q中除了C之外的點集，即當前點 C 未走訪的點集
[L(Q),ind]=min([L(Q);L(C)+W(C,Q)]);%當前點C已走訪了所有的相鄰的未走訪的點，找出與C相鄰的距離最短的點，記錄最短距離和結點的索引值，更新 L
%如果L(Q)
Z(Q(find(ind==2)))=C; %更新Z, 找出Q中索引值為2的結點，將其父親結點更新為C,至此可以確定C已是走訪過的點了
if T&C==T %若 C 點是終點 T, 不用再計算到其它未走訪的點的最短路徑.先判斷C==T，再判斷&
L=L(T); %最短路徑長度；
road=T;%最短路徑終點；
while T~=S%追溯最短路徑上的點
T=Z(T); %從終點往前尋找其父親結點
road=[road,T]; %從終點開始倒序記錄最短路徑上的結點
end
Z=road(length(road):-1:1); %顛倒次序；
return;
end;
[null, mC]=min(L(Q));
if null==Inf
% disp('到值是Inf的點的路不通！');
Z(find(L==Inf))=nan; %NaN或者nan都是「非數」的意思，「0/0」、「∞/∞」、「0*∞」都會產生這種結果
return;
else
C=Q(mC);% 把未走訪的點集Q中與始點距離最近的點作為新的當前點C;
end
end
end

『陸』 數學最短路徑問題最方便的解法是什麼

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」 ，有時被簡稱作「路徑演算法」 。最常用 的路徑演算法有： Dijkstra 演算法、 A*演算法、 SPFA 演算法、 Bellman-Ford 演算法和 Floyd-Warshall 演算法， 本文主要介紹其中的三種。 最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩 結點之間的最短路徑。 演算法具體的形式包括： 確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。 確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的 問題。 在無向圖中該問題與確定起點的問題完全等同， 在有向圖中該問題等同於把所有路徑 方向反轉的確定起點的問題。 確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。 全局最短路徑問題：求圖中所有的最短路徑。 Floyd 求多源、無負權邊的最短路。用矩陣記錄圖。時效性較差，時間復雜度 O(V^3)。 Floyd-Warshall 演算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種演算法， 可以正確處理有向圖或負權的最短路徑問題。 Floyd-Warshall 演算法的時間復雜度為 O(N^3)，空間復雜度為 O(N^2)。 Floyd-Warshall 的原理是動態規劃： 設 Di,j,k 為從 i 到 j 的只以(1..k)集合中的節點為中間節點的最短路徑的長度。 若最短路徑經過點 k，則 Di,j,k = Di,k,k-1 + Dk,j,k-1； 若最短路徑不經過點 k，則 Di,j,k = Di,j,k-1。 因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。 在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。 Floyd-Warshall 演算法的描述如下： 1.for k ← 1 to n do 2.for i ← 1 to n do 3.for j ← 1 to n do 4.if (Di,k + Dk,j<Di,j) then 5.Di,j ← Di,k + Dk,j; 其中 Di,j 表示由點 i 到點 j 的代價，當 Di,j 為∞表示兩點之間沒有任何連接。 Dijkstra 求單源、無負權的最短路。時效性較好，時間復雜度為 O（V*V+E） 。 源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV） 。 當是稀疏圖的情況時，此時 E=V*V/lgV，所以演算法的時間復雜度可為 O（V^2） 。若是斐波那 契堆作優先隊列的話，演算法時間復雜度，則為 O（V*lgV + E） 。 Bellman-Ford 求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路） ，時效性較好，時間復雜 度 O（VE） 。 Bellman-Ford 演算法是求解單源最短路徑問題的一種演算法。 單源點的最短路徑問題是指：給定一個加權有向圖 G 和源點 s，對於圖 G 中的任意一點 v， 求從 s 到 v 的最短路徑。 與 Dijkstra 演算法不同的是，在 Bellman-Ford 演算法中，邊的權值可以為負數。設想從我們可以 從圖中找到一個環路（即從 v 出發，經過若干個點之後又回到 v）且這個環路中所有邊的權 值之和為負。那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處 理這個負環路，程序就會永遠運行下去。而 Bellman-Ford 演算法具有分辨這種負環路的能力。 SPFA是 Bellman-Ford 的隊列優化，時效性相對好，時間復雜度 O（kE）（k<<V） 。 。 與 Bellman-ford 演算法類似， SPFA 演算法採用一系列的鬆弛操作以得到從某一個節點出發到達圖 中其它所有節點的最短路徑。所不同的是，SPFA 演算法通過維護一個隊列，使得一個節點的 當前最短路徑被更新之後沒有必要立刻去更新其他的節點， 從而大大減少了重復的操作次數。 SPFA 演算法可以用於存在負數邊權的圖，這與 dijkstra 演算法是不同的。 與 Dijkstra 演算法與 Bellman-ford 演算法都不同，SPFA 的演算法時間效率是不穩定的，即它對於不 同的圖所需要的時間有很大的差別。 在最好情形下，每一個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間復雜度 僅為 O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時演算法退化為 Bellman-ford 演算法，其時間復雜度為 O(VE)。 SPFA 演算法在負邊權圖上可以完全取代 Bellman-ford 演算法， 另外在稀疏圖中也表現良好。 但是 在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的 Dijkstra 演算法，以及 它的使用堆優化的版本。通常的 SPFA 演算法在一類網格圖中的表現不盡如人意。 

『柒』 最短路徑的兩點怎麼找

最短路徑的兩點可以通過一個定義兩點之間直線最短來決定最短的路徑。

地理信息系統簡稱GIS，是一種以採集、存儲、管理、分析和描述地球表面與地理分布有關數據的空間信息系統。它能顯示數據的空間分布，並具有強大的空間查詢、分析、模擬、統計和預測等功能。故尋求兩點之間最短、最快或景點最多的路徑可應用GIS的查詢和分析功能。

最短路徑介紹

最短路徑問題是圖論研究中的一個經典演算法問題， 旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。 演算法具體的形式包括：確定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。

確定終點的最短路徑問題 - 與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。

『捌』 找最短路徑的方法

1），深度或廣度優先搜索演算法（解決單源最短路徑）
從起始結點開始訪問所有的深度遍歷路徑或廣度優先路徑，則到達終點結點的路徑有多條，取其中路徑權值最短的一條則為最短路徑。
給定一個帶權有向圖G=（V,E），其中每條邊的權是一個實數。另外，還給定V中的一個頂點，稱為
源。
現在要計算從源到其他所有各頂點的最短路徑長度。這里的長度就是指路上各邊權之和。這個問題通
常稱為單源最短路徑 問題。
從起始結點開始訪問所有的深度遍歷路徑或廣度優先路徑，則到達終點結點的路徑有多條，取其中路
徑權值最短的一條則為最短路徑

『玖』 C語言求兩點之間的最短路徑

#include<graphics.h>
#include<stdio.h>
# define n 6
# define NULL 0
#define UP 72
#define DOWN 80
#define ESC 27
#define Enter 13
int i1=0,j1=3,m1=0,n1=0;
int start=0;
char str2[][100]={"THE INTRODUTION OF THE ROUTINE !",
"AUGMENT THE RELATIVE DATA !",
"SEARCH FOR THE INFORMATION !",
"QUIT THE ROUTINE !"};
char str3[][100]={"THE ROUTINE WAS PROGRAMED IN ",
" 2006--07--10",
"PROGRAMER : ",
"CAO JUN BIN "};

int dd[n+1][n+1], pp[n+1][n+1],a[n];
typedef struct
{int number;<br> int edge[n+1][n+1];<br> }graph;
graph g;
int maxdist=2000,mindist;
struct viewpoint
{int x;<br> int y;<br> int number;<br> char inf[10];<br> }bd[n];

struct point
{int number;<br> int x_1;<br> int y_1;<br> }point[n];
typedef struct point f;
struct path
{int V1;<br> int V2;<br> int length;<br> }p[n*n/2];

void mainmenu ();
void con();
void choosepoint() ;
void interface();
void interface1();
void again();
void drawbuilding();
void drawedge();
void floyd(graph g,int m, int dd[n+1][n+1],int pp[n+1][n+1]);
void display(int i,int j,int pp[n+1][n+1],int dd[n+1][n+1]);
void drawpath();
void buildingmap( );
void pathmap( );
main()
{ int gdriver=9,gmode=2;
initgraph(&gdriver,&gmode,"c:\\TURBOC2");
mainmenu();
}

void mainmenu ()
{int a,flag=1,i,j;<br> char c; char str[10];<br> setbkcolor(BLACK);<br> setcolor(LIGHTGRAY);<br> rectangle(20,20,600,475);<br> settextstyle(4,0,4);<br> setcolor(LIGHTRED);<br> outtextxy(160,70,"THE MAIN MENU ");<br> settextstyle(3,0,1);<br> setcolor(CYAN);<br> outtextxy(160,160,str2[0]);<br> outtextxy(160,200,str2[1]);<br> outtextxy(160,240,str2[2]);<br> outtextxy(160,280,str2[3]);<br> while(flag){ c=getch();<br> switch(c){case DOWN:i1++;j1++;<br> m1=i1%4;n1=j1%4;<br> con();break;<br> case UP :if(i1==-1)i1=3;if(j1==-1)j1=3;<br> m1=i1%4;n1=j1%4;a=m1;m1=n1;n1=a;<br> con();<br> i1--;j1--;break;<br> case ESC :flag=0;break;<br> case Enter:cleardevice();<br> if(m1==0){interface1();getch();cleardevice();<br> mainmenu();<br> }

if(m1==1){ setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(20,20,600,475);
rectangle(30,30,590,465) ;
setcolor(LIGHTRED);
settextstyle(3,0,1);
setcolor(LIGHTRED);
outtextxy(160,160,"PLESE CHOOSE THE SEVICE !");
outtextxy(120,200," AUGMENT THE INFORMATION OF THE BUILDING (B)!");
outtextxy(120,240," AUGMENT THE INFORMATION OF THE BUILDING (P) !");
switch(getch()){case'B':{cleardevice();buildingmap();cleardevice();};break;
case 'P':{cleardevice();pathmap();cleardevice();};break;
default: cleardevice();mainmenu();}
}
if(m1==2){
interface();
getch();}
if(m1==3){exit(0);<br> }
}

}

}
void con()
{setcolor(YELLOW);<br> outtextxy(160,160+m1*40,str2[m1]);<br> setcolor(CYAN);<br> outtextxy(160,160+n1*40,str2[n1]);<br> }
void interface()
{ int i,j;
char str[10];
setbkcolor(BLACK);
setcolor(LIGHTGRAY);
rectangle(20,20,600,100);
rectangle (20,20,600,470);
rectangle (20,100,450,470) ;
rectangle(20,350,450,470);
rectangle(20,100,300,350);
settextstyle(3,0,3);
outtextxy(200,30,"WELCOME TO");
outtextxy(120,60,"NORTHEAST DIANLI UNIVERSITY!") ;
outtextxy(460,200,"FROM : ___");
outtextxy(485,250,"TO : ___");
settextstyle(2,0,5);
rectangle(475,315,535,335);
rectangle(475,365,535,385);
outtextxy(455,150,"(PLEASE INPUT!)");
outtextxy(175,360,"THE RESULT !");
outtextxy(500,320,"F");
outtextxy(500,370,"Q");
outtextxy(480,400,"Input");
outtextxy(460,420, "the number 1-->6");
setcolor(RED);
drawbuilding();
drawedge();
i=0;
while(i<'1'||i>'6') i=getch();
sprintf(str,"%c",i);
outtextxy(560,205,str);
while(j<'1'||j>'6') j=getch();
sprintf(str,"%c",j);
outtextxy(560,255,str);
i=i-48;j=j-48;
floyd(g,n,dd[n+1][n+1],pp[n+1][n+1]);
display (i,j,pp[n+1][n+1], dd[n+1][n+1]);
drawpath( );
}
void interface1()
{
setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(20,20,600,475);
rectangle(30,30,590,465) ;
settextstyle(4,0,4);
setcolor(LIGHTRED);

settextstyle(3,0,1);
setcolor(LIGHTRED);
outtextxy(160,160,str3[0]);
outtextxy(160,200,str3[1]);
outtextxy(210,240,str3[2]);
outtextxy(210,280,str3[3]);

}

void again()
{int i;<br> if(start==0) {for (i=0;i<300;i++) delay(1000);}
}

void drawbuilding()
{ int i,a;char str[10];
FILE *fp;
if ((fp=fopen("map.dat","r"))==NULL)
{
printf("Can not open the file of map.dat.\n");
exit(0);
}

for(i=0;i<n;i++)
{fread(&bd[i],sizeof(struct viewpoint),1,fp);<br> point[i].number=bd[i].number;<br> point[i].x_1=bd[i].x;<br> point[i].y_1=bd[i].y;<br><br> setcolor(RED);<br> a=bd[i].number;<br> sprintf(str,"%d",a);<br> again();<br> circle(bd[i].x,bd[i].y,8);<br> setcolor(LIGHTGRAY);<br> outtextxy(bd[i].x-2,bd[i].y-5,str);<br> outtextxy(310,i*30+120,str);<br> outtextxy(325,i*30+120,":");<br> outtextxy(340,i*30+120,bd[i].inf);<br> again();<br> }

fclose(fp);

}

void drawedge()
{ FILE *fp;char str[10];
int i,j,x1,x2,y1,y2,a;
if((fp=fopen("pmap.dat","r"))==NULL)
{ printf ("can't open the file\n");
exit(0);
}

for (i=0;i<=n;i++)
{for (j=0;j<=n;j++)<br> g.edge[i][j]=maxdist;}
for(j=1;j<=n;j++)
g.edge[j][j]=0;
while(!feof(fp))
{ fread(&p[i],sizeof(struct path),1,fp);
if(p[i].V1!=0)
{
{g.edge[p[i].V1][p[i].V2]=p[i].length;<br> g.edge[p[i].V2][p[i].V1]=p[i].length;<br> }
setcolor(LIGHTBLUE);
for(j=0;j<n;j++)
{if(p[i].V1-point[j].number==0)<br> {x1=point[j].x_1;<br> y1=point[j].y_1;<br> }
}

for(j=0;j<n;j++)
{if(p[i].V2==point[j].number)<br> { x2=point[j].x_1;<br> y2=point[j].y_1;<br> }

}
line(x1,y1,x2,y2);
setcolor(LIGHTGRAY);
a=p[i].length;
sprintf(str,"%d",a);
outtextxy((x1+x2)/2,(y1+y2)/2,str);
again();
}
}

fclose(fp);
start=1;
}

void floyd(graph g,int m,int dd[n+1][n+1],int pp[n+1][n+1])
{int i,j,k,w;<br><br>for(i=0;i<=m;i++)<br> {for(j=0;j<=m;j++)<br> dd[i][j]=maxdist;}

for(i=0;i<=m;i++)
{for(j=0;j<=m;j++)<br> pp[i][j]=0;<br> }
for(i=1;i<=m;i++)
{ for(j=1;j<=m;j++)
{dd[i][j]=g.edge[i][j];<br> if(dd[i][j]<maxdist&dd[i][j]!=0)<br> pp[i][j]=j;<br> else<br> pp[i][j]=-1;<br><br> } }
for(k=1;k<=m;k++)
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
if(dd[i][j]>(dd[i][k]+dd[k][j]))
{
dd[i][j]=dd[i][k]+dd[k][j];
pp[i][j]=k;
pp[j][i]=k;
}
}
void display(int i,int j,int pp[n+1][n+1],int dd[n+1][n+1])
{
int pre,flag,k,w=40;int m=0;
int str[10];
pre=k=j;
do { pre=pp[i][pre];
if(pre!=k)
sprintf(str,"%d",k);
outtextxy(120+w,390,str);

outtextxy(130+w,390,"<--");
a[m]=k;
m=m+1;
w=w+40;
k=pre;
pre=pp[i][pre];
flag=pre;
}while(flag!=k) ;

sprintf(str,"%d",flag);
outtextxy(120+w,390,str);
a[m]=flag;
outtextxy(130+w,390,"<--");
sprintf(str,"%d",i);
outtextxy(160+w,390,str);
a[m+1]=i;
a[m+2]=NULL;

outtextxy(60,390,"THE WAY IS:");
outtextxy(60,420,"THE SHORTEST WAY IS :");
sprintf(str,"%d",dd[i][j]);
outtextxy(240,420,str);

}
void drawpath( )
{ int i,j,x1,x2,y1,y2;
char l;
setcolor(RED);
for(i=0;i<n;i++)
{if(a[i+1]!=NULL)<br> { again();<br> for(j=0;j<n;j++)<br> {if(a[i]-point[j].number==0)<br> {x1=point[j].x_1;<br> y1=point[j].y_1;<br> }
}

for(j=0;j<n;j++)
{if(a[i+1]==point[j].number)<br> { x2=point[j].x_1;<br> y2=point[j].y_1;<br> }

}
line(x1,y1,x2,y2);

}
}
i=0;
while(i!='Q'&i!='F'&i!='q'&i!='f') i=getch();
switch(i)
{ case 'Q': {cleardevice();<br> mainmenu();};break;
case 'q': {cleardevice();<br> mainmenu();};break;
case 'F': {cleardevice();interface();};break;
case 'f': {cleardevice();interface();};break;
}
}

void buildingmap( )
{ FILE *fp;
int i;
setbkcolor(BLACK);
setcolor(YELLOW);
rectangle(100,40,450,475);
rectangle(110,50,440,465) ;

setcolor(LIGHTRED);
settextstyle(2,0,4);
setcolor(LIGHTRED); if((fp=fopen("ss1-map","ab"))==NULL)
{ printf ("can't open the file\n");
exit(0);
}
outtextxy(160,100,"Please input the information of the building! ");
for(i=0;i<n;i++)
{ outtextxy(160,100+20*(i+1),"<--input data:" );
scanf("%d,%d,%d,%s\n",&bd[i].x,&bd[i].y,&bd[i].number,bd[i].inf );
if(fwrite(&bd[i],sizeof(struct viewpoint),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if(getch()=='Q') {cleardevice();mainmenu();}
}
void pathmap()
{FILE *fp;<br> int i;<br> cleardevice();<br> setbkcolor(BLACK);<br> rectangle(100,40,450,475);<br> rectangle(110,50,440,465) ;<br><br> setcolor(LIGHTRED);<br> settextstyle(2,0,4);<br> if((fp=fopen("pp1-map","ab"))==NULL)<br> { printf ("can't open the file\n");<br> exit(0);<br> }
fseek(fp,0L,2);
outtextxy(160,100,"Please input the information of the building! ");
for(i=0;i<(n*n/2);i++)
{ outtextxy(160,100+20*(i+1),"<--input data:" );
scanf("%d,%d,%d\n",&p[i].V1,&p[i].V2,&p[i].length );
if(fwrite(&p[i],sizeof(struct path),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if(getch()=='Q') {cleardevice();mainmenu();}
}