《图-邻接表-迪杰斯特拉算法-C语言(共6页).doc》由会员分享，可在线阅读，更多相关《图-邻接表-迪杰斯特拉算法-C语言(共6页).doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上图的邻接表实现迪杰斯特拉算法（C语言）/*迪杰斯特拉算法（狄斯奎诺算法）解决的是从源点到其它所有顶点的最短路径问题*/算法实现：#include #include #define MAX 20#define MAX_FLOAT_NUM 1000 /*最大浮点数（假设最大浮点数是1000）*/typedef int infoType; /*定义边表结点权值的数据的数据类型*/typedef int vertexType; /*定义顶点结点上存储的数据的数据类型*/定义边表结点结构体typedef struct edgenode int adjvertex; /边表结点域
2、infoType info; /边表结点权值，这里存放的是其父结点到该结点的距离struct edgenode *next; /指向下一个邻接点的指针域 EdgeNode;/定义顶点结点结构体typedef struct vertexnode vertexType boolval; /* 顶点结点域，这里存放的是该结点是否找到其距源顶点最短路径的标记，若找到最短路径，则该值为1，否则该值为0 */EdgeNode *firstedge; /边表头指针 VertexNode;typedef struct VertexNode adjlistMAX; /*邻接表*/int vertexNum; /
3、*顶点数*/int edgeNum; /*边数*/ ALGraph; /adjacency list graph:邻接表/*函数名称：CreateGraph函数功能：创建邻接表输入：顶点数vertexNum，边数edgeNum输出：指向已创建好的邻接表的指针*/ALGraph* CreateGraph(int vertexNum, int edgeNum) int k;EdgeNode *p; /声明图的邻接表ALGraph *G;G = (ALGraph *)malloc(sizeof(ALGraph);if (!G) G = NULL;else G-vertexNum = vertexNu
4、m;G-edgeNum = edgeNum;/建立顶点表for (k = 0; k vertexNum; k +) G-adjlistk.boolval = 0; /*boolval值判断该结点到源结点的距离是否是最短距离，是1表示已达最短距离，是0表示还没有达最短距离*/G-adjlistk.firstedge = NULL;/建立边表printf(请输入顶点、其邻接顶点和权值信息：n);for(k = 0; k edgeNum; k +) int i, j;infoType info;/表现的是边的关系，有多少对就有多少边，所以for循环次数为G-edgeNumscanf(%d,%d,%d
5、,&i,&j,&info); if (i != j) p = (EdgeNode *)malloc(sizeof(EdgeNode);p-next = G-adjlisti.firstedge;G-adjlisti.firstedge = p;p-adjvertex = j;p-info = info;return G;/*函数名称：dijkstra（迪杰斯特拉/迪斯奎诺）函数功能：实现迪杰斯特拉算法，找出每个顶点到源定点u的最短距离输入：邻接表指针G，源顶点u，记录每个顶点到源顶点的最短距离的数组d，到源顶点的最短路径上的前方顶点编号p输出：记录每个顶点到源顶点的最短距离的数组d，到源顶点的
6、最短路径上的前方顶点编号p*/void dijkstra(ALGraph *G, int u, int d, int p) int i,j,t;EdgeNode *pnode;/初始化参数for (i = 0; i vertexNum; i +) /G-adjlisti.boolval = 0; di = MAX_FLOAT_NUM;pi = -1;/更新源顶点直接子结点到源结点的最短距离if (!(pnode = G-adjlistu.firstedge) return;while (pnode) dpnode-adjvertex = pnode-info;ppnode-adjvertex
7、= u;pnode = pnode-next;G-adjlistu.boolval = 1;du = 0;/更新所有除源结点外的结点到源结点的最短距离for (i = 1; i vertexNum; i +) int min = MAX_FLOAT_NUM;t = u;/在所有结点中找出一个距离源结点距离最小的一个结点for (j = 0; j vertexNum; j +) if (G-adjlistj.boolval != 1 & min dj) t = j;min = dj;if (t = u) /顶点到达不了源顶点（距离为MAX_FLOAT_NUM）或者顶点已经找到了到源顶点的最短路径
8、（boolval值为1）break;G-adjlistt.boolval = 1;/*找到一个距离源结点距离最小的结点时，将该结点看成是一个源结点，更新它的所有直接子结点到源结点u的最短距离di，然后再去找一个距离源结点距离最小的结点，如此反复的更新所有结点到源结点的最短距离。*/pnode = G-adjlistt.firstedge;while (pnode) if (G-adjlistpnode-adjvertex.boolval != 1) & (dpnode-adjvertex (dt + pnode-info) dpnode-adjvertex = dt + pnode-info;
9、ppnode-adjvertex = t;pnode = pnode-next;/主函数int main()ALGraph * G;int vertexNum, edgeNum; /图的邻接表的顶点数和边数int u; /源顶点编号int *d = NULL; /动态数组，各顶点到源顶点的最短路径int *p = NULL; /动态数组，存放到源顶点的最短路径上的前方顶点编号int i, j, k, t; int *tmp;printf(请输入顶点个数和边个数：n);scanf(%d,%d,&vertexNum,&edgeNum);printf(n);G = CreateGraph(verte
10、xNum, edgeNum);if (!G) printf(G为空！n);return 0;d = (int *)malloc(sizeof(int) * vertexNum);p = (int *)malloc(sizeof(int) * vertexNum);printf(请输入源结点：n);scanf(%d,&u);printf(n);/调用迪杰斯特拉算法函数dijkstra(G, u, d, p);tmp = (int *)malloc(sizeof(int) * (vertexNum + 1);printf(各点到源顶点%d的距离：n, u);for (i = 0; i = 0; k -) printf(%dt, tmpk);printf(nn);printf(n);free(G);return 0;运行结果：专心-专注-专业