}

}

輸出沒(méi)有列車或飛機(jī)從城市v0到v1；

 }

 

 

·         求城市v0，v1之間的最少時(shí)間算法的偽碼描述如下：

        TimeDispose( )

{for(v=0；v<城市個(gè)數(shù)；v++)

         {城市v還未求得最少時(shí)間；

          *(D+v)=城市v0到v的最少時(shí)間；

          將城市v的路徑設(shè)置為空；

          if(*(D+v)<INFINITY)

           將城市v0和v加入到城市v的路徑中；

         }

         城市v0到城市v0的最少時(shí)間為0；

         城市v0設(shè)為已求得最少時(shí)間；

         for(i=1；i<城市個(gè)數(shù)；v++)

         {m=INFINITY;

          for(w=0；w<城市個(gè)數(shù)；w++)

           if(城市w未求得最少時(shí)間)

            if(*(D+w)<m)

            {v=w;

             m=*(D+w);

            }

if(v等于v1)

{根據(jù)城市v的路徑輸出從城市v0到城市v1所需經(jīng)過(guò)的城市及路線；

 輸出最少時(shí)間v1；

  返回；

}

else

{將城市v設(shè)為已求得最少時(shí)間；

 for(w=0；<G.vexnum；w++)

  if(城市w未求得最少時(shí)間并且從城市v到w有路徑)

  {保存城市w原來(lái)的路徑；

將城市w的路徑設(shè)為城市v的路徑并在最后加入城市w；

   利用時(shí)間樹(shù)求出從城市v0城市w的最少時(shí)間及路徑；

   if(*(D+w)>從城市v0到城市w的最少時(shí)間)

    *(D+w)=從城市v0到城市w的最少時(shí)間；

   else

    將城市w的路徑還原；

  }

}

         }

        }

        輸出沒(méi)有列車或飛機(jī)從城市v0到v1；

       }

 

六．測(cè)試分析
   按照附錄中的測(cè)試數(shù)據(jù)，得出如下測(cè)試、分析結(jié)果：

1.       操作員管理功能.

1>. 當(dāng)我們從鍵盤(pán)輸入有關(guān)圖的頂點(diǎn)及弧的信息后,用顯示圖的函數(shù)驗(yàn)證,DOS中顯示的圖的信息與從鍵盤(pán)輸入的信息相同,表明交通系統(tǒng)可以從鍵盤(pán)正確輸入信息.

2>. 我們事先建立了有關(guān)圖的3 個(gè)文本文件(包括city.txt,plan.txt,train.txt),在交通系統(tǒng)程序中,選擇從文本文件輸入圖的信息后,用顯示操作驗(yàn)證,表明文本文件的內(nèi)容可以正確調(diào)入圖的結(jié)構(gòu)體中,說(shuō)明交通系統(tǒng)可以從文本文件中讀取信息.

3>. 當(dāng)從鍵盤(pán)或文本文件初始化交通圖后,測(cè)試增加或刪除城市結(jié)點(diǎn),增加或刪除航班或列車弧,以上各功能都正確.

2.  交通咨詢功能.

   1>. 火車情況.

        1.1>.最少費(fèi)用.

a.       兩地間無(wú)中轉(zhuǎn)且有多輛火車.

北京----à鄭州

輸出結(jié)果為:

旅行路線是:  

乘坐NO.27列車車次在13：15 從 Beijing 到zhengzhou.

最少旅行費(fèi)用是78元.     

                    而若選擇NO.41 則花費(fèi)為80 元.  

                  結(jié)果正確.

 

b.       兩地之間無(wú)中轉(zhuǎn)達(dá)且只有一輛火車.

西安----à武漢

輸出結(jié)果為:

   旅行路線是:  

乘坐NO.218列車車次在1：34從xi’an到wuhan.

                                   最少旅行費(fèi)用是178.00 元.     

                                    結(jié)果正確.

c.        兩地之間有中轉(zhuǎn).

昆明----à北京

輸出結(jié)果為:

   旅行路線是:  

乘坐NO.323列車車次在16.：31從kunming到Guangzhou.

                                   乘坐NO.59列車車次在3：39從Guangzhou 到shanghai.

乘坐NO.41列車車次在0：35從shanghai 到zhengzhou.

乘坐NO.27列車車次在13：42 從zhengzhou 到Beijing.

最少旅行費(fèi)用是462 元.    

                             而若選擇 昆明---à武漢---à蘭州---à北京 則花費(fèi)為506 元.

   若選擇 昆明---à武漢---à西安---à鄭州---à北京 則花費(fèi)為472 元.

結(jié)果正確.

 

          1.2>最短時(shí)間.

     a. 兩地間無(wú)中轉(zhuǎn)且有多輛火車.

北京----à鄭州

輸出結(jié)果為:

旅行路線是:  

乘坐NO.41列車車次在13：15從Beijing 到zhengzhou.

最少旅行時(shí)間是7：57.    

                    結(jié)果正確.

b.兩地之間無(wú)中轉(zhuǎn)達(dá)且只有一輛火車.

烏魯木齊----à蘭州 

輸出結(jié)果為:

   旅行路線是:  

乘坐No.371列車車次在0：35從wulumuqi 到lanzhou.

                                   最少旅行時(shí)間是10：48.   

                                    結(jié)果正確.

c.       兩地之間有中轉(zhuǎn).

廣州----à蘭州 

輸出結(jié)果為:

   旅行路線是:  

乘坐NO.59列車車次在3：39從guangzhou到shanghai.

                                   乘坐NO.41列車車次在0：35從shanghai到zhengzhou.

乘坐NO.41列車車次在9.40從zhengzhou到Beijing.

乘坐NO.134列車車次在19.24從Beijing到lanzhou.

最少旅行時(shí)間是54：49.     

        結(jié)果正確.

  

               1.3>.最短周轉(zhuǎn)次數(shù).

 

                      a. 兩地可直達(dá)且有中轉(zhuǎn).

                             昆明---à廣州

    輸出結(jié)果為:

旅行路線是:  

乘坐NO.323列車車次在16：31從kunming到guangzhou.

最少旅行中轉(zhuǎn)次數(shù)是0次 .

                  而若選擇 昆明---à武漢---à長(zhǎng)沙---à蘭州 則 結(jié)果為3.

結(jié)果正確.

                      b.兩地間有多條中轉(zhuǎn)路徑.

                          昆明---à上海

   輸出結(jié)果為:

旅行路線是:  

乘坐NO.323列車車次在16：31從kunming 到guangzhou.

乘坐NO.59列車車次在3：39從guangzhou 到shanghai.

最少旅行總轉(zhuǎn)次數(shù)是1次 .

                  而若選擇 昆明---à武漢---à西安---à鄭州---à上海 則 結(jié)果為4.

結(jié)果正確.

 

2.飛機(jī)情況.

 

            2.1>.兩地?zé)o直達(dá).

           蘭州---à武漢

                      輸出結(jié)果為:

                       不存在飛機(jī)航班從lanzhou到wuhan.

 

           2.2>.兩地?zé)o直達(dá).

                     拉薩---à昆明

                     a.最少費(fèi)用:

                 輸出結(jié)果為:

乘坐NO.173飛機(jī)航班在10：20 從lasa 到kunming.

                      最少旅行費(fèi)用是830 元.

                      結(jié)果正確.

b.最短時(shí)間:

輸出結(jié)果為:

乘坐NO.173 飛機(jī)航班在10：20 從lasa 到kunming.

                      最少旅行時(shí)間是1：25.

結(jié)果正確.

                      c.最短中轉(zhuǎn)次數(shù).

輸出結(jié)果為:

乘坐NO.173 飛機(jī)航班在10：20 從lasa 到kunming.

                      最少旅行中轉(zhuǎn)次數(shù)是0次.

結(jié)果正確.

 

            2.3>兩地可中轉(zhuǎn).

                    廣州----à北京

                a.最少費(fèi)用:  

輸出結(jié)果為:

乘坐NO.2323飛機(jī)航班在10：15 從Guangzhou 到xi’an.

                      乘坐NO.210 飛機(jī)航班在12：35 從xi’an 到beijing.

最少旅行費(fèi)用是2250 元.

                    結(jié)果正確.

 

b.最短時(shí)間:

輸出結(jié)果為:

   乘坐NO.2323 飛機(jī)航班在10：15 從Guangzhou 到xi’an.

                            乘坐NO.210 飛機(jī)航班在12：35 從xi’an 到beijing.

最少旅行時(shí)間是4：00.

 

    結(jié)果正確.

                      c.最短中轉(zhuǎn)次數(shù).

輸出結(jié)果為:

乘坐NO.2323 飛機(jī)航班在10：15 從Guangzhou 到xi’an.

                      乘坐NO.210 飛機(jī)航班在12：35從xi’an 到beijing.

最少旅行中轉(zhuǎn)次數(shù)是1次.

結(jié)果正確.

3.打印

  打印結(jié)果正確;

4.退出

能正確退出

 

七．使用說(shuō)明
      1．運(yùn)行程序，首先出現(xiàn)主界面。主界面包括四個(gè)選項(xiàng)：選項(xiàng)一：管理員管理界面，選擇該項(xiàng)可進(jìn)行城市交通系統(tǒng)的管理，具體使用說(shuō)明見(jiàn)說(shuō)明2；選項(xiàng)二：用戶咨詢界面，選擇該項(xiàng)可進(jìn)行最少費(fèi)用、最少時(shí)間、最少中轉(zhuǎn)次數(shù)的決策咨詢，具體使用見(jiàn)說(shuō)明7；選項(xiàng)三：顯示城市交通系統(tǒng)程序，選擇該項(xiàng)可顯示城市交通系統(tǒng)的所有信息，包括城市、航班和列車車次；選項(xiàng)四：退出程序，選擇該項(xiàng)將退出程序。

      2．管理員管理界面包括5個(gè)選項(xiàng)：選項(xiàng)一：初始化城市交通系統(tǒng)界面，可進(jìn)行城市交通系統(tǒng)的初始化，具體使用見(jiàn)說(shuō)明3；選項(xiàng)二：城市編輯界面，可進(jìn)行城市的增加和刪除，具體使用見(jiàn)說(shuō)明4；選項(xiàng)三：航班編輯界面，可進(jìn)行航班的增加和刪除，具體使用見(jiàn)說(shuō)明5；選項(xiàng)四：列車車次編輯界面，可進(jìn)行列車車次的增加和刪除，具體使用見(jiàn)說(shuō)明6；選項(xiàng)五：返回上一級(jí)菜單，可返回主界面。

      3．初始化城市交通系統(tǒng)界面包括兩個(gè)選項(xiàng)：選項(xiàng)一：通過(guò)鍵盤(pán)初始化城

         市交通系統(tǒng)，選擇該項(xiàng)后程序?qū)⒔o出輸入說(shuō)明，按輸入說(shuō)明用戶需逐

步輸入城市、航班、列車車次的信息來(lái)對(duì)城市交通系統(tǒng)初始化。在輸入航班和列車信息時(shí)需注意兩點(diǎn)：a.所輸入的航班和列車的發(fā)車時(shí)間均在同一天。b.若發(fā)車時(shí)間小于到達(dá)時(shí)間，則說(shuō)明列車在同一天到達(dá)，若發(fā)車時(shí)間大于到達(dá)時(shí)間，則說(shuō)明列車在次日達(dá)到。飛機(jī)航班也是如此；選項(xiàng)二：通過(guò)文檔初始化城市交通系統(tǒng)，選擇該項(xiàng)可用文檔進(jìn)行初始化，但文檔必須存在于程序的同一目錄下，且必須包含CITY，PLANE，TRAIN三個(gè)文本文檔，否則程序?qū)⑻崾境鲥e(cuò)。

      4．城市編輯界面包括兩個(gè)選項(xiàng)：選項(xiàng)一：增加城市，可在城市交通系統(tǒng)中加入新的城市，若用戶輸入的是已有的城市名，程序?qū)⑻崾境鲥e(cuò)；選項(xiàng)二：刪除城市，可在城市交通系統(tǒng)中刪除城市，用戶必須輸入一個(gè)已有的城市名，否則程序提示出錯(cuò)。     

      5．航班編輯界面包括兩個(gè)選項(xiàng)：選項(xiàng)一：增加航班，可在兩個(gè)城市之間

         新增航班，選擇該項(xiàng)后用戶需輸入新增航班的編號(hào)，起始城市，到達(dá)

城市及費(fèi)用、時(shí)間等信息；選項(xiàng)二，刪除航班，可刪除兩個(gè)城市間的

一條航班，選擇該項(xiàng)后用戶需輸入要?jiǎng)h除航班的編號(hào)，起始城市，到

達(dá)城市的信息，若航班不存在或編號(hào)、城市輸入有誤，程序?qū)⑻崾惧e(cuò)

誤。

      6．列車車次編輯界面包括兩個(gè)選項(xiàng)：選項(xiàng)一：增加列車車次，可在兩個(gè)

城市之間新增列車車次，選擇該項(xiàng)后用戶需輸入新增列車的編號(hào)，起

始城市，到達(dá)城市及費(fèi)用、時(shí)間等信息；選項(xiàng)二，刪除列車車次，可

刪除兩個(gè)城市間的一條列車車次，選擇該項(xiàng)后用戶需輸入要?jiǎng)h除車次

的編號(hào)，起始城市，到達(dá)城市的信息，若列車車次不存在或編號(hào)、城

市輸入有誤，程序?qū)⑻崾惧e(cuò)誤。

      7．用戶咨詢界面包括四個(gè)選項(xiàng)：選項(xiàng)一：最少費(fèi)用咨詢；選項(xiàng)二：最少時(shí)間咨詢；選項(xiàng)三：最少中轉(zhuǎn)次數(shù)咨詢；選項(xiàng)三：返回上級(jí)菜單，可返回主界面。選擇選項(xiàng)一、二、三都要求用戶輸入咨詢信息，包括起始城市，到達(dá)城市和交通工具。輸入完畢后城市提示用戶是否確認(rèn)，若不確認(rèn)則要求用戶重新輸入咨詢信息，若確認(rèn)則給出用戶所需的最優(yōu)決策信息。

      

八．附錄：測(cè)試數(shù)據(jù)
                      航班時(shí)刻表

  

機(jī)  號(hào)                      
 出 發(fā) 地 
 到 達(dá) 地
 出發(fā)時(shí)間
 到達(dá)時(shí)間
 費(fèi)  用  
 
6320
 北京

上海
 上海

北京
 16：20

18：00   
 17：25

19：05
 680元
 
2104
 北京

烏魯木齊
 烏魯木齊

  北京
 8：00

10：45
 9：55

11：40
 1150元
 
201
   北京

  西安
   西安

  北京
 15：25

12：35
 17：00

14：15
 930元
 
2323
   西安

廣州
   廣州

  西安
 7：15

10：15
 9：35

11：35
 1320元
 
173
   拉薩

  昆明
   昆明

拉薩
 10：20

12：35
 11：45

14：00
 830元
 
3304
   拉薩

  武漢
   武漢

拉薩
 14：15

16：25
 15：45

17：55
 890元
 
82
   烏魯木齊

    昆明
   昆明

烏魯木齊  
 9：30

13：05
 12：15

15：50
 1480元
 
4723
   武漢

廣州
  廣州

 武漢 
 7：05

11：25
 8：45

13 ：05
 810元
 

 

          

                     列車時(shí)刻表

車 次
 出 發(fā) 地 
 到 達(dá) 地
 出發(fā)時(shí)間
 到達(dá)時(shí)間
 車   費(fèi)
 
27
 北京

鄭州

西安

鄭州
  鄭州

 西安

鄭州

北京

 
 13：15

21：24

05：41

13：42
 21：12

05：13

13：30

21：39
   78元

  82元

82元

78元
 
41
  北京

 鄭州

 上海

 鄭州
  鄭州

上海

鄭州

北京
 7：11

15：20

00：35

09：40
 15：08

00：13

09：28

17：37
   90元

  100元

  100元

90元
 
59
  上海

廣州
  廣州

 上海
 08：20

03：39
 03：16

22：53
   182元
 
134
  蘭州

 北京
  北京

 蘭州
 03：52

19：24
 18：56

10：28
   162元
 
323
  廣州

 昆明
  昆明

 廣州
 06：18

16：31
 16：14

02：27
   102元
 
873
  武漢

 昆明
  昆明

 武漢
 07：13

21：42
 21：17

11：46
 134元
 
116
  武漢

 長(zhǎng)沙
  長(zhǎng)沙

 武漢
 9：36

18：54
 18：32

03：48

 
 98元
 
373
  長(zhǎng)沙

 廣州
  廣州

 長(zhǎng)沙
 13：15

00：35
 00：15

11：35
 116元
 
 

747
 蘭州

武漢
 武漢

蘭州
 17：41

15：13
 14：47

12：19
 210元
 
371
  蘭州

烏魯木齊
  烏魯木齊

  蘭州
 11：42

00：35
 23：54

11：23
 114元
 
218
 武漢

西安
  西安

 武漢
 18：50

01：34
 11：51

18：35
 178元