国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【C語言\數(shù)據(jù)結(jié)構(gòu)】圖dijkstra最短路徑 鄰接矩陣（無項(xiàng)、有權(quán)）代碼簡(jiǎn)單實(shí)現(xiàn)深度解析

2年前作者：妖精七七_(dá)分類：Toy博客閱讀(33)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【C語言\數(shù)據(jù)結(jié)構(gòu)】圖dijkstra最短路徑 鄰接矩陣（無項(xiàng)、有權(quán)）代碼簡(jiǎn)單實(shí)現(xiàn)深度解析。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

這個(gè)代碼是在圖的鄰接矩陣（無項(xiàng)、有權(quán)）的代碼的基礎(chǔ)上，添加了dijkstra最短路徑函數(shù)，并且修改測(cè)試用例和主函數(shù)代碼，圖的鄰接矩陣（無項(xiàng)、有權(quán)）的代碼具體請(qǐng)查看 【C語言\數(shù)據(jù)結(jié)構(gòu)】圖之鄰接矩陣（無向、有權(quán)）代碼簡(jiǎn)單實(shí)現(xiàn)，這里就不過多贅述。

dijkstra最短路徑實(shí)現(xiàn)思路

我們用一個(gè)案例來解釋dijkstra最短路徑的思路：

采用書上第 161 頁定義的圖的鄰接矩陣存儲(chǔ)表示,編程實(shí)現(xiàn)產(chǎn)生最短路徑的 dijkstra,C語言，數(shù)據(jù)結(jié)構(gòu),算法,圖論,數(shù)據(jù)結(jié)構(gòu)

引入問題：求A頂點(diǎn)到達(dá)其他頂點(diǎn)的最短路徑長(zhǎng)度和最短路徑。

引入定義：一個(gè)頂點(diǎn)到達(dá)其他頂點(diǎn)的直接距離的最小值就是最短路徑。

例如，A頂點(diǎn)可以到達(dá)BDEF四個(gè)頂點(diǎn)，直接距離分別是AB2,AD4,AE3,AF5，這些距離的最短直接距離是AB2，則AB2就是最短路徑。

因?yàn)槿绻阆霃腁到達(dá)其他頂點(diǎn)再從其他頂點(diǎn)到達(dá)B，第一步的距離一定要比AB這個(gè)直接距離大，所以AB就是最短路徑。

接著我們引入judgment[i]和dist[i]和path[i]一維數(shù)組，分別表示A頂點(diǎn)到i頂點(diǎn)最短路徑有無確定，A頂點(diǎn)到i頂點(diǎn)的最短路徑，和該最短路徑中i頂點(diǎn)的前一個(gè)頂點(diǎn)的下標(biāo)。

首先我們?cè)L問A頂點(diǎn)，把A頂點(diǎn)到其他頂點(diǎn)的直接距離，修正到dist數(shù)組中，也就是目前A頂點(diǎn)到其他頂點(diǎn)的最短路徑長(zhǎng)度，path數(shù)組都存儲(chǔ)A，因?yàn)槟壳暗淖疃搪窂街?，各頂點(diǎn)的前一個(gè)頂點(diǎn)的下標(biāo)就是A。

接著我們找到最短的直接距離，依據(jù)定義我們知道AB就是A到B的最短路徑，把judgment[B]修正為true，表示A到B的最短路徑已經(jīng)確定，然后訪問B頂點(diǎn)，看看A到B再由B頂點(diǎn)到其他頂點(diǎn)的距離，會(huì)不會(huì)比目前存儲(chǔ)的dist最短路徑還要小，如果還要小，就修正dist和path數(shù)組。

第一步，訪問A頂點(diǎn)，得到：

采用書上第 161 頁定義的圖的鄰接矩陣存儲(chǔ)表示,編程實(shí)現(xiàn)產(chǎn)生最短路徑的 dijkstra,C語言，數(shù)據(jù)結(jié)構(gòu),算法,圖論,數(shù)據(jù)結(jié)構(gòu)

第二步：找到dist中最小的值，這個(gè)值的judgement必須為false，已經(jīng)確定的最短路徑就不需要訪問了。把judgement[B]置true，由B頂點(diǎn)修正dist和path。B頂點(diǎn)到C頂點(diǎn)距離是2，ABC距離一共是4，比dist存儲(chǔ)的無窮要小，就修正dist，接著修正path。

采用書上第 161 頁定義的圖的鄰接矩陣存儲(chǔ)表示,編程實(shí)現(xiàn)產(chǎn)生最短路徑的 dijkstra,C語言，數(shù)據(jù)結(jié)構(gòu),算法,圖論,數(shù)據(jù)結(jié)構(gòu)

第三步：在還沒有確定最短路徑的頂點(diǎn)中，找dist最小的值，EF隨便選一個(gè)，再由E頂點(diǎn)修正其他沒有確定最短路徑的頂點(diǎn)的dist和path，由于E只能到D或者A，A頂點(diǎn)最短路徑已經(jīng)確定不考慮，ED是2,2+3=5大于4，所以不用修正。

采用書上第 161 頁定義的圖的鄰接矩陣存儲(chǔ)表示,編程實(shí)現(xiàn)產(chǎn)生最短路徑的 dijkstra,C語言，數(shù)據(jù)結(jié)構(gòu),算法,圖論,數(shù)據(jù)結(jié)構(gòu)

第四步：F中找到dist最小的頂點(diǎn)F，把F頂點(diǎn)的judgmen改為T，再通過F頂點(diǎn)修正dist和path，由于F只能到A或者B，AB的最短路徑已經(jīng)確定，不考慮。

采用書上第 161 頁定義的圖的鄰接矩陣存儲(chǔ)表示,編程實(shí)現(xiàn)產(chǎn)生最短路徑的 dijkstra,C語言，數(shù)據(jù)結(jié)構(gòu),算法,圖論,數(shù)據(jù)結(jié)構(gòu)

第五步：在judgment為F的頂點(diǎn)中找到dist最小的頂點(diǎn)，CD選一個(gè)C，judgement改為T，由C頂點(diǎn)修正剩下judgment為F的頂點(diǎn)，C可以到BD,B最短路徑已經(jīng)確定不考慮，CD是2,C的dist4+2大于D的dist，不修正。

采用書上第 161 頁定義的圖的鄰接矩陣存儲(chǔ)表示,編程實(shí)現(xiàn)產(chǎn)生最短路徑的 dijkstra,C語言，數(shù)據(jù)結(jié)構(gòu),算法,圖論,數(shù)據(jù)結(jié)構(gòu)

第六步：

采用書上第 161 頁定義的圖的鄰接矩陣存儲(chǔ)表示,編程實(shí)現(xiàn)產(chǎn)生最短路徑的 dijkstra,C語言，數(shù)據(jù)結(jié)構(gòu),算法,圖論,數(shù)據(jù)結(jié)構(gòu)

編寫dijkstra最短路徑函數(shù)

 

void dijkstra(graph g, int v, int dist[], int path[]) {
    bool judgment[MAX];
    for (int i = 1; i <= g.vexnum; i++) {
        judgment[i] = false;
        dist[i] = g.arcs[v][i];
        if (dist[i] < INFINITY || i == v) {
            path[i] = v;
        } else {
            path[i] = -1;
        }
    }
    
     dist[v] = 0;
    judgment[v] = true;
    
     for (int i = 1; i < g.vexnum; i++) {
        int min = INFINITY;
        int index_min;
        for (int j = 1; j <= g.vexnum; j++) {
            if (judgment[j] == false && dist[j] < min) {
                index_min = j;
                min = dist[j];
            }
        }
        judgment[index_min] = true;
        for (int j = 1; j <= g.vexnum; j++) {
            if (judgment[j] == false && dist[j] > (dist[index_min] + g.arcs[index_min][j]) && (dist[index_min] + g.arcs[index_min][j]) < INFINITY) {
                dist[j] = dist[index_min] + g.arcs[index_min][j];
                path[j] = index_min;
            }
        }
    }
 }
 

初始化操作
 

 
 
void dijkstra(graph g, int v, int dist[], int path[])
 

 

傳入圖g，以及v頂點(diǎn)下標(biāo)，dist一維數(shù)組表示v頂點(diǎn)分別到其他頂點(diǎn)的最短路徑長(zhǎng)度，path一維數(shù)組表示v頂點(diǎn)分別到其他頂點(diǎn)的最短路徑中終點(diǎn)的前一個(gè)頂點(diǎn)。
 

 
 
bool judgment[MAX]
 

 

創(chuàng)建一個(gè)判斷數(shù)組，用來判斷每一個(gè)頂點(diǎn)是否是最短路徑，數(shù)據(jù)類型是bool型，如果已經(jīng)確定頂點(diǎn)v到該頂點(diǎn)的最短路徑，對(duì)應(yīng)下標(biāo)存儲(chǔ)true，反之存儲(chǔ)false。
 

 
 
????bool?judgment[MAX];
 ????for?(int?i?=?1;?i?<=?g.vexnum;?i++)?{
 ????????judgment[i]?=?false;
 ????????dist[i]?=?g.arcs[v][i];
 ????????if?(dist[i]?<?INFINITY?||?i?==?v)?{
 ????????????path[i]?=?v;
 ????????}?else?{
 ????????????path[i]?=?-1;
 ????????}
 ????}
 

 

初始化judgement，dist，path數(shù)組，首先對(duì)v頂點(diǎn)做處理，遍歷每一個(gè)頂點(diǎn)，judgement初始值全部置false，dist數(shù)組數(shù)據(jù)全部更新為v頂點(diǎn)直接到其他各頂點(diǎn)的距離，如果v頂點(diǎn)到i頂點(diǎn)的邊存在，或者v頂點(diǎn)自己到自己，則v頂點(diǎn)到i頂點(diǎn)的前一個(gè)頂點(diǎn)置為v，否則path置-1表示這條邊不存在，這樣就完成了對(duì)v頂點(diǎn)的訪問，即初始化。
 

循環(huán)遍歷維護(hù)dist和path
 

 
 
dist[v] = 0; judgment[v] = true;
 

 

先把v頂點(diǎn)到自己的最短路徑值0，對(duì)應(yīng)judgment值置true，表示已經(jīng)確定v頂點(diǎn)到自己的最短路徑。
 

 
 
for?(int?i?=?1;?i?<?g.vexnum;?i++)?{
 ????????int?min?=?INFINITY;
 ????????int?index_min;
 ????????for?(int?j?=?1;?j?<=?g.vexnum;?j++)?{
 ????????????if?(judgment[j]?==?false?&&?dist[j]?<?min)?{
 ????????????????index_min?=?j;
 ????????????????min?=?dist[j];
 ????????????}
 ????????}
 ????????judgment[index_min]?=?true;
 ????????for?(int?j?=?1;?j?<=?g.vexnum;?j++)?{
 ????????????if?(judgment[j]?==?false?&&?dist[j]?>?(dist[index_min]?+?g.arcs[index_min][j])?)?{
 ????????????????dist[j]?=?dist[index_min]?+?g.arcs[index_min][j];
 ????????????????path[j]?=?index_min;
 ????????????}
 ????????}
 ????}
 

 

最外層的循環(huán)僅表示以下內(nèi)容需要循環(huán)g.vexnum-1次，也就是除去v頂點(diǎn)訪問過的，其他頂點(diǎn)都需要訪問一次。
 

 
 
????????int?min?=?INFINITY;
 ????????int?index_min;
 ????????for?(int?j?=?1;?j?<=?g.vexnum;?j++)?{
 ????????????if?(judgment[j]?==?false?&&?dist[j]?<?min)?{
 ????????????????index_min?=?j;
 ????????????????min?=?dist[j];
 ????????????}
 ????????}
 
 
????????judgment[index_min]?=?true;
 

 

找到v頂點(diǎn)到其他頂點(diǎn)j直接距離的最短距離，這個(gè)距離即是v頂點(diǎn)到j(luò)頂點(diǎn)的最短路徑，因?yàn)槿绻阆霃钠渌窂降絡(luò)頂點(diǎn)，第一步走的路徑一定要比v頂點(diǎn)直接到j(luò)頂點(diǎn)的距離長(zhǎng)，所以這個(gè)最短的直接距離就是最短路徑，找到v頂點(diǎn)到index_min頂點(diǎn)的最短路徑，就訪問該頂點(diǎn)，并且維護(hù)對(duì)應(yīng)judgment的值，表示v頂點(diǎn)到index_min頂點(diǎn)的最短路徑已經(jīng)確定。
 

 
 
????????for?(int?j?=?1;?j?<=?g.vexnum;?j++)?{
 ????????????if?(judgment[j]?==?false?&&?dist[j]?>?(dist[index_min]?+?g.arcs[index_min][j])?)?{
 ????????????????dist[j]?=?dist[index_min]?+?g.arcs[index_min][j];
 ????????????????path[j]?=?index_min;
 ????????????}
 ????????}
 

 

訪問index_min頂點(diǎn)，根據(jù)這個(gè)頂點(diǎn)，看看能不能找到還沒有確定的到達(dá)其他頂點(diǎn)的最短路徑頂點(diǎn)的更小距離，維護(hù)dist和path數(shù)組。
 

如果這個(gè)j頂點(diǎn)的最短路徑還沒確定，并且v頂點(diǎn)到index_min頂點(diǎn)的最短路徑，加上頂點(diǎn)index_min到j(luò)的路徑長(zhǎng)度比dist存儲(chǔ)的v頂點(diǎn)到j(luò)頂點(diǎn)的最短路徑還要小，就維護(hù)dist的值，并且把這個(gè)還沒確定的最短路徑的j的前一個(gè)頂點(diǎn)的下標(biāo)維護(hù)到path數(shù)組。
 

依次循環(huán)，訪問剩下的頂點(diǎn)，維護(hù)dist和path。
 


 

編寫主函數(shù)
 

 

int main() {
    graph g;
    int start,end;
    initGraph(g);
    createGraph(g);
    showGraph(g);
    printf("\n輸入起點(diǎn)和終點(diǎn)：\n");
    scanf("%d%d",&start,&end);
    int dist[MAX];//dist[i]  v頂點(diǎn)到i定點(diǎn)最短路徑的距離
    int path[MAX];//path[i]  v頂點(diǎn)到i定點(diǎn)最短路徑中i的上一個(gè)頂點(diǎn)下標(biāo)
    dijkstra(g, start, dist, path);
    
     printf("\n");
    printf("dist:\n");
    for(int i=1;i<=g.vexnum;i++){
        printf("%d ",dist[i]);
    }
    printf("\n");
    printf("path:\n");
    for(int i=1;i<=g.vexnum;i++){
        printf("%d ",path[i]);
    }
    
     printf("\n\n最短路徑長(zhǎng)度：\n%d\n",dist[end]);
    
     char pathText[MAX]={""};
    
     int cur=end;
    pathText[strlen(pathText)]=end+'0';
    while(cur!=start){
        pathText[strlen(pathText)]=path[cur]+'0';
        cur=path[cur];
    }
    
     printf("%d到%d的最短路徑：\n",start,end);
    
     for(int i=strlen(pathText)-1;i>=0;i--){
        printf("%c ",pathText[i]);
    }
    printf("\n");
 }
/*測(cè)試用例：
 5 8
 1 2 1
 1 5 4
 1 3 3
 2 4 2
 4 5 4
 3 4 1
 2 3 2
 3 5 1
 */
 

 
 
printf("\n\n最短路徑長(zhǎng)度：\n%d\n",dist[end]);
 ????
 ????char?pathText[MAX]={""};
 ????
 ????int?cur=end;
 ????pathText[strlen(pathText)]=end+'0';
 ????while(cur!=start){
 ????????pathText[strlen(pathText)]=path[cur]+'0';
 ????????cur=path[cur];
 ????}
 

 

字符數(shù)組這樣初始化，可以利用strlen函數(shù)計(jì)算自己的長(zhǎng)度，以達(dá)到尾插的效果。
 

先把end終點(diǎn)頂點(diǎn)尾插進(jìn)pathText
 

接著循環(huán)變量path數(shù)組，直到cur到start為止，這樣最短路徑的逆路程就存儲(chǔ)在pathText數(shù)組中了。
 

 
 
????printf("%d到%d的最短路徑：\n",start,end);
 ????
 ????for(int?i=strlen(pathText)-1;i>=0;i--){
 ????????printf("%c?",pathText[i]);
 ????}
 ????printf("\n");
 

 

接下來只要從后往前遍歷就可以正向輸出最短路徑了。
 



完整代碼
 

 

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

#define MAX 100
 #define INFINITY 9999
enum graphType {DG, UG, DN, UN}; //圖的類型定義：有向圖，無向圖，有向網(wǎng)，無項(xiàng)網(wǎng)
typedef char vertexType;
typedef struct {
    vertexType vexs[MAX];
    int arcs[MAX][MAX];
    int vexnum, arcnum;
    graphType kind;
 } graph;

void initGraph(graph &g) {
    g.kind = UN;
    printf("輸入頂點(diǎn)數(shù)和邊數(shù)：\n");
    scanf("%d%d", &g.vexnum, &g.arcnum);
    for (int i = 1; i <= g.vexnum; i++) {
        g.vexs[i] = i;
    }
    for (int i = 1; i <= g.vexnum; i++) {
        for (int j = 1; j <= g.vexnum; j++) {
            if (i == j) g.arcs[i][j] = 0;
            else g.arcs[i][j] = INFINITY;
        }
    }
 }

void createGraph(graph &g) {
    int start_index, end_index, weight;


    printf("輸入每條邊的起點(diǎn)終點(diǎn)下標(biāo)和邊的權(quán)重：\n");
    for (int i = 1; i <= g.arcnum; i++) {
        scanf("%d%d%d", &start_index, &end_index, &weight);
        g.arcs[start_index][end_index] = weight;
        g.arcs[end_index][start_index] = weight;
    }
 }

void showGraph(graph &g) {
    printf("鄰接矩陣：\n");
    for (int i = 1; i <= g.vexnum; i++) {
        for (int j = 1; j <= g.vexnum; j++) {
            printf("%d ", g.arcs[i][j]);
        }
        printf("\n");
    }
 }

void dijkstra(graph g, int v, int dist[], int path[]) {
    bool judgment[MAX];
    for (int i = 1; i <= g.vexnum; i++) {
        judgment[i] = false;
        dist[i] = g.arcs[v][i];
        if (dist[i] < INFINITY || i == v) {
            path[i] = v;
        } else {
            path[i] = -1;
        }
    }
    
     dist[v] = 0;
    judgment[v] = true;
    
     for (int i = 1; i < g.vexnum; i++) {
        int min = INFINITY;
        int index_min;
        for (int j = 1; j <= g.vexnum; j++) {
            if (judgment[j] == false && dist[j] < min) {
                index_min = j;
                min = dist[j];
            }
        }
        judgment[index_min] = true;
        for (int j = 1; j <= g.vexnum; j++) {
            if (judgment[j] == false && dist[j] > (dist[index_min] + g.arcs[index_min][j]) && (dist[index_min] + g.arcs[index_min][j]) < INFINITY) {
                dist[j] = dist[index_min] + g.arcs[index_min][j];
                path[j] = index_min;
            }
        }
    }
 }


int main() {
    graph g;
    int start,end;
    initGraph(g);
    createGraph(g);
    showGraph(g);
    printf("\n輸入起點(diǎn)和終點(diǎn)：\n");
    scanf("%d%d",&start,&end);
    int dist[MAX];//dist[i]  v頂點(diǎn)到i定點(diǎn)最短路徑的距離
    int path[MAX];//path[i]  v頂點(diǎn)到i定點(diǎn)最短路徑中i的上一個(gè)頂點(diǎn)下標(biāo)
    dijkstra(g, start, dist, path);
    
     printf("\n");
    printf("dist:\n");
    for(int i=1;i<=g.vexnum;i++){
        printf("%d ",dist[i]);
    }
    printf("\n");
    printf("path:\n");
    for(int i=1;i<=g.vexnum;i++){
        printf("%d ",path[i]);
    }
    
     printf("\n\n最短路徑長(zhǎng)度：\n%d\n",dist[end]);
    
     char pathText[MAX]={""};
    
     int cur=end;
    pathText[strlen(pathText)]=end+'0';
    while(cur!=start){
        pathText[strlen(pathText)]=path[cur]+'0';
        cur=path[cur];
    }
    
     printf("%d到%d的最短路徑：\n",start,end);
    
     for(int i=strlen(pathText)-1;i>=0;i--){
        printf("%c ",pathText[i]);
    }
    printf("\n");
 }
/*測(cè)試用例：
 5 8
 1 2 1
 1 5 4
 1 3 3
 2 4 2
 4 5 4
 3 4 1
 2 3 2
 3 5 1
 */
 

代碼運(yùn)行截圖：
 

采用書上第 161 頁定義的圖的鄰接矩陣存儲(chǔ)表示,編程實(shí)現(xiàn)產(chǎn)生最短路徑的 dijkstra,C語言，數(shù)據(jù)結(jié)構(gòu),算法,圖論,數(shù)據(jù)結(jié)構(gòu)
 



結(jié)尾
 

我們今天學(xué)習(xí)了dijkstra最短路徑的實(shí)現(xiàn)，過程一共有三個(gè)一維數(shù)組judgement，dist和path，分別表示最短路徑是否確定，最短路徑長(zhǎng)度，最短路徑前一個(gè)頂點(diǎn)的下標(biāo)。一個(gè)定義：一個(gè)頂點(diǎn)到達(dá)其他頂點(diǎn)的直接距離的最小值就是最短路徑。依次訪問dist最小值頂點(diǎn)，這個(gè)頂點(diǎn)的judgement需要為false，然后把這個(gè)fals改為true，接著由這個(gè)頂點(diǎn)修正其他false頂點(diǎn)的dist和path，依次循環(huán)。
 
 

最后，感謝您閱讀我的文章，希望這些內(nèi)容能夠?qū)δ兴鶈l(fā)和幫助。如果您有任何問題或想要分享您的觀點(diǎn)，請(qǐng)隨時(shí)在評(píng)論區(qū)留言。
 

同時(shí)，不要忘記訂閱我的博客以獲取更多有趣的內(nèi)容。在未來的文章中，我將繼續(xù)探討這個(gè)話題的不同方面，為您呈現(xiàn)更多深度和見解。
 

謝謝您的支持，期待與您在下一篇文章中再次相遇！文章來源地址http://www.zghlxwxcb.cn/news/detail-774109.html
到了這里，關(guān)于【C語言\數(shù)據(jù)結(jié)構(gòu)】圖dijkstra最短路徑 鄰接矩陣（無項(xiàng)、有權(quán)）代碼簡(jiǎn)單實(shí)現(xiàn)深度解析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！
領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用
相關(guān)文章
覺得文章有用就打賞一下文章作者
支付寶掃一掃打賞
博客贊助
微信掃一掃打賞
請(qǐng)作者喝杯咖啡吧~博客贊助
支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)
二維碼1
領(lǐng)取紅包
二維碼2
領(lǐng)紅包