- 题目
- 贝尔曼福德算法
- 思想
- 代码实现
- 有向无环图单元最短路径
- 思想
- 代码实现
题目
贝尔曼福德算法 思想
说白了就是把每条边都松弛一遍，如果有负回路就报错。
松弛操作如下：
课件中的伪代码：
C语言实现贝尔曼福德算法：
#include有向无环图单元最短路径 思想#define MAX_VERTEX 10 #define INF 999999 typedef struct v DataType; //顶点信息数据结构 struct v{ int d; //距离 int num; //序号 struct v *p; //父节点 }; //邻接矩阵表示图（数组） struct MGraph { DataType vertex[MAX_VERTEX];//顶点信息 int arc[MAX_VERTEX][MAX_VERTEX];//临接矩阵 int vertexNum, arcNum; //顶点个数，边个数 }; //图的构造函数,输入：顶点信息，顶点个数，边个数 void CreateMGraph(DataType v[], int n, int e){ int i, j, vi, vj, w, result; //循环变量i，j；顶点vi，vj struct MGraph G; //创建一个图 G.vertexNum = n; //图的顶点数 G.arcNum = e; //图的边数 for(i = 0; i < G.vertexNum; i++){ //初始化图的顶点信息 G.vertex[i].d = v[i].d; G.vertex[i].p = v[i].p; G.vertex[i].num = i; } for (i = 0; i < G.vertexNum; i++){ for(j = 0; j < G.vertexNum; j++){ G.arc[i][j] = 0; //初始化邻接矩阵 } } printf("若两个顶点相邻则输入这两个顶点并且输入权值：n"); for(i = 0; i < G.arcNum; i++){ scanf("%d %d %d",&vi, &vj, &w); G.arc[vi][vj] = w; //邻接则等于权值 } //进行贝尔曼福德算法 Bellman_Ford(G, 0); } //进行贝尔曼福德算法：输入图，开始顶点号 void Bellman_Ford(struct MGraph G, int n){ G.vertex[n].d = 0; //将初始结点的值设置为零 int i, j, k, m; DataType *p ; for(i = 0; i < G.vertexNum - 1; i++){ for(j = n; j < G.vertexNum + n; j++){ //从前选择的顶点开始进行松弛 if(j == G.vertexNum){ //如果对选择顶点之后的顶点结束之后就回到第一个结点操作 for(m = 0; m < G.vertexNum - n + 1; m++){ for(k = 0; k < G.vertexNum; k++){ if(G.arc[m][k] != 0){ //对边进行松弛操作 if((G.vertex[m].d + G.arc[m][k]) < G.vertex[k].d){ G.vertex[k].d = G.vertex[m].d + G.arc[m][k]; G.vertex[k].p = &G.vertex[m]; p = &G.vertex[k]; } } } } } else{//对选择顶点之后的点进行操作 for(k = 0; k < G.vertexNum; k++){ if(G.arc[j][k] != 0){ //对条边进行松弛操作 if((G.vertex[j].d + G.arc[j][k]) < G.vertex[k].d){ G.vertex[k].d = G.vertex[j].d + G.arc[j][k]; G.vertex[k].p = &G.vertex[j]; p = &G.vertex[k]; } } } } } } //如果图中存在权值为负数的回路则无法完成贝尔曼福德算法，报错 for(i = 0; i < G.vertexNum - 1; i++){ for(j = 0; j < G.vertexNum; j++){ if(G.arc[i][j] != 0 && G.vertex[j].d > G.vertex[i].d + G.arc[i][j]){ printf("错误，图中有权值为负的回路！n"); } } } //输出结果 for(i = 0; i < G.vertexNum; i++){ printf("顶点%d的值为：%dn",i, G.vertex[i].d); } printf("最短路径为：n"); while(p != NULL){ if(i > 1) printf("%d<-",p->num); else printf("%d",p->num); p = p->p; i--; } } int main(){ int i; //循环变量 int n, e; //顶点个数与边个数 DataType v[MAX_VERTEX]; printf("请输入顶点个数与边的个数："); scanf("%d %d",&n, &e); for(i = 0; i < n; i++){//初始化顶点信息 v[i].d = INF; //开始设置为无限远 v[i].p = NULL; //父节点为空 } //创建图并开始进行贝尔曼福德算法 CreateMGraph(v, n, e); return 0; }
先对图进行DFS（深度优先搜索），保存结果，成功一个拓扑排序的链表，再初始化图，按照链表对图中的每个节点的邻居进行松弛
代码实现课件中的伪代码：
C语言实现有向无环图单元最短路径：
#include#include #define MAX_VERTEX 10 typedef struct v DataType; int time = 0; typedef struct LNode{ int Data; //数据域 int no; //序号 struct LNode *Next; //指针域 }LNode,*LinkList; LinkList L = NULL; //顶点信息数据结构 struct v{ int no; //序号 int dist; //距离 int c; //状态颜色 1白，2灰， 3黑 int d, f; //开始时间，结束时间 struct v *p; //父节点 struct v *s; //子节点 }; //邻接矩阵表示图（数组） struct MGraph { DataType vertex[MAX_VERTEX];//顶点信息 int arc[MAX_VERTEX][MAX_VERTEX];//临接矩阵 int vertexNum, arcNum; //顶点个数，边个数 }; //图的构造函数,输入：顶点信息，顶点个数，边个数 void CreateMGraph(DataType v[], int n, int e){ int i, j, vi, vj, w; //循环变量i，j；顶点vi，vj struct MGraph G; //创建一个图 G.vertexNum = n; //图的顶点数 G.arcNum = e; //图的边数 for(i = 0; i < G.vertexNum; i++){ //初始化图的顶点信息 G.vertex[i].c = v[i].c; G.vertex[i].f = v[i].f; G.vertex[i].d = v[i].d; G.vertex[i].no = v[i].no; G.vertex[i].p = v[i].p; G.vertex[i].dist = v[i].dist; } for (i = 0; i < G.vertexNum; i++){ for(j = 0; j < G.vertexNum; j++){ G.arc[i][j] = 0; //初始化邻接矩阵 } } printf("若两个顶点相邻则输入这两个顶点并且输入权值：n"); for(i = 0; i < G.arcNum; i++){ scanf("%d %d %d",&vi, &vj, &w); G.arc[vi][vj] = w; //邻接则为权值 } DFS(G); //进行深度优先搜索 PrintList(L); //输出结果 DAG_Shortest_Paths(G, 1, L); //单元最短路径 } void DFS(struct MGraph G){ int i; time = 0; LinkList L; for(i = 0; i < G.vertexNum; i++){ if(G.vertex[i].c == 1){ DFS_visit(&G, &G.vertex[i]); //遍历每个顶点，先从0号顶点开始 } } } void DFS_visit(struct MGraph *G, DataType *u){ int i, j; time++; u->d = time; u->c = 2; //顶点被访问变成2（灰色） for(i = 0; i < G->arcNum; i++){ if(G->arc[u->no][i] != 0){ //若邻接表不为0则表示两点之间有边，则进行访问。 if(G->vertex[i].c == 1){ //当顶点状态为1（白）则进行访问 G->vertex[i].p = &u; DFS_visit(G, &G->vertex[i]); //递归 } } } u->c = 3; //顶点的邻居都被访问后，顶点状态信息变成3（黑色） time++; u->f = time; //结束时间 head_insert(u->no,u->dist ,L); } void head_insert(int x, int dist, LinkList L){ //头插法 LinkList s; s=(LNode*)malloc(sizeof(LNode)); s->no=x; s->Data = dist; s->Next=L->Next; L->Next=s; //插入结点 } void PrintList(LinkList L) //输出一个拓扑排序 { LinkList p; p=L->Next; printf("拓扑排序如下：n"); while(p!=NULL) { printf("%d ",p->no); //输出拓扑排序的顶点序号 p=p->Next; } printf("n"); } //单源最短路径算法，输入：有向图，开始的顶点号，拓扑排序后的链表 void DAG_Shortest_Paths(struct MGraph G, int n, LinkList L){ int i, no; LinkList p; DataType *q; p=L->Next; for(i = 0; i < n; i++){ //选择从第几号顶点开始 p=p->Next; } G.vertex[p->no].dist = 0; //初始化顶点 while(p != NULL){ no = p->no; for(i = 0; i < G.vertexNum; i++){ if(G.arc[no][i] != 0){ //松弛操作 if((G.vertex[no].dist + G.arc[no][i]) < G.vertex[i].dist){ G.vertex[i].dist = G.vertex[no].dist + G.arc[no][i]; G.vertex[i].p = &G.vertex[no]; G.vertex[no].s = &G.vertex[i]; q = &G.vertex[i]; } } } p=p->Next; } //输出结果 printf("有向无环图结果为：n"); for(i = 0;i < G.vertexNum; i++){ printf("点%d的值为%dn", i, G.vertex[i].dist); } printf("路径为n"); i = G.vertexNum; while(q != NULL){ if(i > 1+n) printf("%d<-",q->no); else printf("%d",q->no); q = q->p; i--; } } int main(){ int i; //循环变量 int n, e; //顶点个数与边个数 DataType v[MAX_VERTEX]; L = (LNode*)malloc(sizeof(LNode)); //创建头结点 L->Next=NULL; printf("请输入顶点个数与边的个数："); scanf("%d %d",&n, &e); for(i = 0; i < n; i++){//初始化顶点信息 v[i].c = 1; v[i].d = 0; v[i].f = 0; v[i].no = i; v[i].p = NULL; v[i].dist = 99999; //无穷大 } //创建图并开始进行单源最短路径算法 CreateMGraph(v, n, e); return 0; }
