離散數(shù)學大作業(yè)?

——利用Floyd算法計算兩城市間最優(yōu)路徑及距離?

代碼在最下面

一．提出問題

在交通網(wǎng)絡(luò)非常發(fā)達、交通工具和交通方式不斷更新的今天,人們在出差、旅游或做其他出行時，不僅關(guān)心節(jié)省交通費用，而且對里程和所需要的時間等問題也感興趣。對于這樣一個人們關(guān)心的問題，可用一個圖結(jié)構(gòu)來表示交通網(wǎng)絡(luò)系統(tǒng)，利用計算機建立一個交通咨詢系統(tǒng)。圖中的頂點表示城市，邊表示城市之間的交通關(guān)系。這個交通系統(tǒng)可以回答出行旅客提出的各種路徑選擇問題。例如，問題之一：“一位旅客要從 A 城到 B 城，他希望選擇一條路徑最短”。設(shè)計一個程序，實現(xiàn)對兩個城市最短路徑的查詢。

二．模型化

精力有限，顧及不到所有城市在地圖上選取了18個城市作為圖的結(jié)點，

?

代碼實現(xiàn)過程用漢字比較繁瑣，所以在此將18個城市標號0-17進行路徑問題的計算

?

為了盡量體現(xiàn)Floyd算法的計算過程，在次假定只有結(jié)點周圍的且不超過1000km的城市有有向邊，邊的長度設(shè)為百度地圖所搜索到的最短路程，剩余的城市間距離設(shè)置為最大值5000km，即不可直接到達。

例如合肥的有向邊鏈接了鄭州、南京、武漢、南昌，雖然合肥離上海、杭州也很近，但在此為了突出Floyd算法，不賦予該兩座城市之間的邊，而是借助南京這個結(jié)點到達。

（人手搜索，按序號找，手敲的，真的累死我了啊啊啊啊啊啊?。?

之后通過Floyd算法計算各個城市間最短距離，并且記錄路徑，最后格式化輸出。

三.??編程實現(xiàn)

1、城市代號與名字匹配結(jié)構(gòu)體構(gòu)建

?

結(jié)構(gòu)體Vnode，用于存儲城市名字字符串，之后再通過城市代號，達到輸出漢字的效果，使呈現(xiàn)更明確

2、靜態(tài)變量

（啃了之前寫noj數(shù)據(jù)結(jié)構(gòu)實驗11題的老本）

int lu[maxnum][maxnum][maxnum]：第一個值設(shè)為a，第二個值設(shè)為b，第三個值設(shè)為c，a，b用于定位某個節(jié)點到某個節(jié)點，c用于記錄路線，即，數(shù)組用于記錄某個節(jié)點到各個節(jié)點最短路徑的途經(jīng)節(jié)點。
wei[maxnum][maxnum]：用于記錄lu[maxnum][maxnum][maxnum]數(shù)組的路徑最前端此時位于第幾個位置，便于更新途徑節(jié)點

3、主函數(shù)模塊

?

函數(shù)調(diào)用關(guān)系如圖

4、城市名初始化函數(shù)模塊

（沒選到的城市無意冒犯，全部省會弄下來我會死的????，隨便選了18個城市）

標號與城市名對應如圖

5、路徑距離初始化代碼

?

（5000即不可直達）

6、路徑初始化函數(shù)模塊

路徑初始都設(shè)為出發(fā)結(jié)點和到達結(jié)點，暫且不考慮不可達情況，不影響后續(xù)結(jié)果。

7、Floyd算法函數(shù)模塊

for循環(huán)最里層在完成路徑長度的更新同時，完成了路徑途經(jīng)結(jié)點的更新，是Floyd函數(shù)的進化版本。

8、檢測輸入結(jié)點并輸出路徑長度及路徑模塊

m記錄需要求多少條路徑。

temp1[maxnum],temp2[maxnum]分別記錄初末結(jié)點。

格式化輸出。

9、輸入輸出測試

先輸入整數(shù)n，表示要求多少組路徑

然后n行輸入a?b表示要求從a?->?b的路徑

四.?形成結(jié)論文章來源地址http://www.zghlxwxcb.cn/news/detail-499675.html

1. 成功利用Floyd算法、c語言程序?qū)崿F(xiàn)了對18個城市之間最短路徑及長度的計算以及格式化輸出。
2. 缺點：初始的輸入因本人時間有限，沒能完成將輸入也改成漢字輸入，所以要求兩城市路徑要先看城市對應代號然后輸入。
3. 通過這次大作業(yè)，我更加深刻地理解了離散課上所教授的Floyd算法，實現(xiàn)了教學合一，而不是單純的聽老師講課或是機械地寫書上的習題，老師與別的班的不同教學任務富含特色，著實令我印象深刻，感謝老師栽培。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxnum 20
#define maxlu 5000

typedef struct Vnode{
	char name[10];
}AdjList[maxnum];

AdjList cheng;

int lu[maxnum][maxnum][maxnum];
int wei[maxnum][maxnum];

void chu()
{
    strcpy(cheng[0].name,"北京");
    strcpy(cheng[1].name,"天津");
    strcpy(cheng[2].name,"太原");
    strcpy(cheng[3].name,"西寧");
    strcpy(cheng[4].name,"蘭州");
    strcpy(cheng[5].name,"西安");
    strcpy(cheng[6].name,"鄭州");
    strcpy(cheng[7].name,"成都");
    strcpy(cheng[8].name,"武漢");
    strcpy(cheng[9].name,"合肥");
    strcpy(cheng[10].name,"南京");
    strcpy(cheng[11].name,"上海");
    strcpy(cheng[12].name,"杭州");
    strcpy(cheng[13].name,"重慶");
    strcpy(cheng[14].name,"長沙");
    strcpy(cheng[15].name,"南昌");
    strcpy(cheng[16].name,"昆明");
    strcpy(cheng[17].name,"廣州");
}
  //  北，天，太，西，蘭，西，鄭，成，武，合，南，上，杭，重，長，南，昆，廣
int ans[18][18]=
{//  0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,
    {0,137,519,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
    {134,0,540,5000,5000,5000,694,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
    {502,519,0,5000,601,433,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
    {5000,5000,5000,0,222,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
    {5000,5000,5000,218,0,626,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
    {5000,5000,600,5000,643,0,481,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000},
    {5000,709,433,5000,5000,479,0,5000,510,566,662,5000,5000,5000,5000,5000,5000,5000},
    {5000,5000,5000,5000,873,746,5000,0,5000,5000,5000,5000,5000,304,5000,5000,815,5000},
    {5000,5000,5000,5000,5000,5000,513,5000,0,377,533,5000,5000,5000,5000,5000,5000,5000},
    {5000,5000,5000,5000,5000,5000,569,5000,385,0,170,5000,5000,5000,5000,5000,5000,5000},
    {5000,5000,5000,5000,5000,5000,5000,5000,5000,169,0,305,280,5000,5000,5000,5000,5000},//南京
    {5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,308,0,178,5000,5000,5000,5000,5000},
    {5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,279,177,0,5000,5000,531,5000,5000},
    {5000,5000,5000,5000,5000,5000,5000,301,5000,5000,5000,5000,5000,0,888,5000,843,5000},
    {5000,5000,5000,5000,5000,5000,5000,5000,333,5000,5000,5000,5000,905,0,337,5000,5000},
    {5000,5000,5000,5000,5000,5000,5000,5000,342,437,5000,5000,523,5000,337,0,5000,780},
    {5000,5000,5000,5000,5000,5000,5000,815,5000,5000,5000,5000,5000,836,5000,5000,0,5000},
    {5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,5000,676,780,5000,0},
    };

void luchu()
{
    for(int i=0;i<18;i++)
    for(int j=0;j<18;j++)
        wei[i][j]=1;
    for(int i = 0;i < 18;i++)
    {
        for(int j = 0;j < 18;j++)
        {
            lu[i][j][wei[i][j]]=i;
            wei[i][j]++;
            lu[i][j][wei[i][j]]=j;
            wei[i][j]++;
        }
    }
}
void floyd()
{
    int i,j,k;
    for(k = 0;k < 18;k++)
    {
        for(i = 0;i < 18;i++)
        {
            for(j = 0;j < 18;j++)
            {
                if(ans[i][j]>ans[i][k]+ans[k][j] )
                {
                    ans[i][j]=ans[i][k]+ans[k][j];
                    int w;
                    for(w=1;w<wei[i][k];w++)
                    {
                        lu[i][j][w]=lu[i][k][w];     
                    }
                    for(w=2;w<wei[k][j];w++)
                    {
                        lu[i][j][wei[i][k]+w-2]=lu[k][j][w];     
                    }
                    wei[i][j]=wei[i][k]+wei[k][j]-2;
                }
            }
        }
    }
}
 
void print(int m)               //待改
{
    int i;
    int x,y;
    scanf("%d",&m);
    int temp1[maxnum];
    int temp2[maxnum];
    for(i = 0;i < m;i++)
    {
        scanf("%d %d",&temp1[i],&temp2[i]);
    }
    printf("--------------------------------------------\n");
    for(i = 0;i < m;i++)
    {
        printf("%s -> %s 的最優(yōu)路徑長%dkm，最優(yōu)路徑為：\n",cheng[temp1[i]].name,cheng[temp2[i]].name,ans[temp1[i]][temp2[i]]);
        for(int j=1;j<maxnum;j++)
        {
            if(lu[temp1[i]][temp2[i]][j]!=temp2[i])
            printf("%s\n",cheng[lu[temp1[i]][temp2[i]][j]].name);
            else
            {
            printf("%s\n",cheng[lu[temp1[i]][temp2[i]][j]].name);
            printf("--------------------------------------------\n");
            break;
            }
        }
    }
}
int main()
{
    chu();
    int m;
    luchu();
    floyd();
    print(m);
    return 0;
}

到了這里，關(guān)于Floyd算法實現(xiàn)實際問題——18個城市間最優(yōu)路線規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！