#include <stdio.h>#define MAX_VERTEX_NUM 20 //最大頂點個數typedef int VRTYPE, InfoType; typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向圖、有向網、無向圖、無向網} typedef struct ArcCell {VRTYPE adj; //無權圖為0或1; 帶權圖為權值InfoType *info; }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {AdjMatrix arcs; //鄰接矩陣，這里以數組下標唯一標識每個頂點int vexnum, arcnum;GraphKind kind; }MGraph;void create_G(MGraph *G) { int i, j, v;printf("輸入頂點數:\n");scanf("%d", &G->vexnum);printf("輸入弧數:\n");scanf("%d", &G->arcnum);for (int m = 0; m < G->vexnum; m++)for (int n = 0; n < G->vexnum; n++)G->arcs[m][n].adj = -1; //不聯通的弧設置其弧長為-1printf("請按照起點號、終點號、弧長輸入每條弧的信息:\n");for (int k = 0; k < G->arcnum; k++){scanf("%d%d%d", &i, &j, &v); //有弧連接的頂點對以及弧的權重,弧從i指向j(默認有向圖)G->arcs[i][j].adj = v;} }void show_G(MGraph G) //展示創建的鄰接矩陣 {printf("\n創建的鄰接矩陣：\n");for (int m = 0; m < G.vexnum; m++){for (int n = 0; n < G.vexnum; n++)printf("%3d ", G.arcs[m][n].adj);printf("\n");}printf("\n"); }void ShortestPath_DIJ(MGraph G, int v0) //最短路算法 {int D[MAX_VERTEX_NUM];bool S[MAX_VERTEX_NUM] = { false };for (int i = 0; i < G.vexnum; i++)D[i] = G.arcs[v0][i].adj;D[v0] = 0;S[v0] = true;for (int i = 0; i < G.vexnum; i++){int j = 0, min = 0;for (int m = 0; m < G.vexnum; m++) //找出當前必定是最短路的點{if (min == 0 && D[m] != -1 && !S[m]){min = D[m];j = m;}else if (D[m] < min && D[m] != -1 && !S[m]){j = m;}}S[j] = true;for (int k = 0; k < G.vexnum; k++) //更新if (!S[k])if (G.arcs[j][k].adj != -1){if (D[k] == -1)D[k] = D[j] + G.arcs[j][k].adj;else if (D[j] + G.arcs[j][k].adj < D[k])D[k] = D[j] + G.arcs[j][k].adj;}}printf("\n編號為%d頂點到其它頂點的最短路：\n", v0);for (int i = 0; i < G.vexnum; i++)printf("%d ", D[i]); }void main() {MGraph G;create_G(&G);show_G(G);ShortestPath_DIJ(G, 0); }

總結

以上是生活随笔為你收集整理的图的邻接矩阵表示与最短路径算法（ Dijkstra ）代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。