【C语言】AOE网路径算法详解
【算法图例】
待更...
【算法核心思想】
【算法步骤】
【核心代码】
int TopSort(AGraph* g, int ve[], Stack* s1)
{
int i, j, k, n;
int s2[maxSize], top2 = -1;
ArcNode* p;
s1->top = -1;
n = 0;
for (i = 0; i < g->n; ++i)
{
if (g->adjlist[i].count == 0)
s2[++top2] = i;
ve[i] = 0;
}
if (top2 != 0)
{
printf("Fatal Error: Not is AOE");
return 0;
}
while (top2 != -1)
{
j = s2[top2--];
n++;
(s1->top)++;
s1->data[s1->top] = j;
p = g->adjlist[j].firstarc;
while (p != NULL)
{
k = p->adjvex;
(g->adjlist[k].count)--;
if (g->adjlist[k].count == 0)
s2[++top2] = k;
if (ve[j] + p->info > ve[k])
ve[k] = ve[j] + p->info;
p = p->nextarc;
}
}
if (n == g->n)
{
return 1;
}
else
{
printf("Fatal Error: Not is AOE");
return 0;
}
}
int CriticalPath(AGraph* g)
{
int ve[maxSize], vl[maxSize], e[maxSize], l[maxSize];
int i, j, k;
char tag;
ArcNode* p;
Stack s1;
if (!TopSort(g, ve, &s1))
return 0;
for (i = 0; i < g->n; ++i)
{
vl[i] = ve[g->n - 1];
}
while (s1.top != -1)
{
j = s1.data[s1.top];
(s1.top)--;
p = g->adjlist[j].firstarc;
while (p != NULL)
{
k = p->adjvex;
if (vl[k] - p->info < vl[j])
vl[j] = vl[k] - p->info;
p = p->nextarc;
}
}
j = 0;
for (i = 0; i < g->n; ++i)
{
p = g->adjlist[i].firstarc;
while (p != NULL)
{
k = p->adjvex;
e[j] = ve[i];
l[j] = vl[k] - p->info;
tag = (e[j] == l[j]) ? '*' : ' ';
printf("a%2d (%2d,%2d) %2d %2d %c n", j, i, k, e[j], l[j], tag);
j++;
p = p->nextarc;
}
}
return 1;
}
【算法测试】
测试数据：
来源：天勤210页 图7-27 AOE网
格式：
顶点数 边数
顶点号 顶点号 权值
11 15
0 1 3
0 2 4
1 3 2
1 4 1
2 4 3
2 5 5
3 6 6
4 6 8
4 7 4
5 8 2
6 10 7
7 8 10
7 9 4
8 9 1
9 10 6
测试代码：
#include <stdio.h>
#include <stdlib.h>
#define maxSize 100
typedef struct ArcNode
{
int adjvex;
int info;
struct ArcNode* nextarc;
}ArcNode;
typedef struct
{
int count;
ArcNode* firstarc;
}VNode;
typedef struct
{
VNode adjlist[maxSize];
int n, e;
}AGraph;
typedef struct
{
int data[maxSize];
int top;
}Stack;
FILE* fp;
void InsertEdge(AGraph* G, int v1, int v2, int w)
{
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->info = w;
p->nextarc = G->adjlist[v1].firstarc;
G->adjlist[v1].firstarc = p;
}
void CreateGraph(AGraph* G)
{
int nv, ne, i, v1, v2, w;
fp = fopen("C:CodeBlocksProjectAG.txt", "r");
fscanf(fp, "%d%d", &nv, &ne);
for (i = 0; i < nv; i++)
{
G->adjlist[i].firstarc = NULL;
}
for (i = 0; i < ne; ++i)
{
fscanf(fp, "%d%d%d", &v1, &v2, &w);
InsertEdge(G, v1, v2, w);
}
G->e = ne;
G->n = nv;
fclose(fp);
}
void GetIndegree(AGraph* g)
{
int i, j;
int c;
ArcNode* p;
for (i = 0; i < g->n; ++i)
{
c = 0;
for (j = 0; j < g->n; ++j)
{
if (i != j)
{
p = g->adjlist[j].firstarc;
while (p != NULL)
{
if (p->adjvex == i)
{
c++;
break;
}
p = p->nextarc;
}
}
}
g->adjlist[i].count = c;
}
}
int TopSort(AGraph* g, int ve[], Stack* s1)
{
int i, j, k, n;
int s2[maxSize], top2 = -1;
ArcNode* p;
s1->top = -1;
n = 0;
for (i = 0; i < g->n; ++i)
{
if (g->adjlist[i].count == 0)
s2[++top2] = i;
ve[i] = 0;
}
if (top2 != 0)
{
printf("Fatal Error: Not is AOE");
return 0;
}
while (top2 != -1)
{
j = s2[top2--];
n++;
(s1->top)++;
s1->data[s1->top] = j;
p = g->adjlist[j].firstarc;
while (p != NULL)
{
k = p->adjvex;
(g->adjlist[k].count)--;
if (g->adjlist[k].count == 0)
s2[++top2] = k;
if (ve[j] + p->info > ve[k])
ve[k] = ve[j] + p->info;
p = p->nextarc;
}
}
if (n == g->n)
{
return 1;
}
else
{
printf("Fatal Error: Not is AOE");
return 0;
}
}
int CriticalPath(AGraph* g)
{
int ve[maxSize], vl[maxSize], e[maxSize], l[maxSize];
int i, j, k;
char tag;
ArcNode* p;
Stack s1;
if (!TopSort(g, ve, &s1))
return 0;
for (i = 0; i < g->n; ++i)
{
vl[i] = ve[g->n - 1];
}
while (s1.top != -1)
{
j = s1.data[s1.top];
(s1.top)--;
p = g->adjlist[j].firstarc;
while (p != NULL)
{
k = p->adjvex;
if (vl[k] - p->info < vl[j])
vl[j] = vl[k] - p->info;
p = p->nextarc;
}
}
j = 0;
for (i = 0; i < g->n; ++i)
{
p = g->adjlist[i].firstarc;
while (p != NULL)
{
k = p->adjvex;
e[j] = ve[i];
l[j] = vl[k] - p->info;
tag = (e[j] == l[j]) ? '*' : ' ';
printf("a%2d (%2d,%2d) %2d %2d %c n", j, i, k, e[j], l[j], tag);
j++;
p = p->nextarc;
}
}
return 1;
}
int main()
{
AGraph G;
CreateGraph(&G);
GetIndegree(&G);
CriticalPath(&G);
return 0;
}
测试结果：
相关知识
加法接力赛C语言算法,C语言循环结构
基于递归神经网络算法的电子物流配送系统配送路径优化
用c语言写一朵最简单的花
一个简单的C语言程序（详解）
基于正余双弦自适应灰狼优化算法的医药物流配送路径规划
堪称最好最全的A*算法详解（译文）
【C语言】预处理(预编译)详解(上)（C语言最终篇）
C语言情人节玫瑰花代码
C语言：输出所有的水仙花数
物流配送路径规划模型及其改进TLBO算法研究
网址: 【C语言】AOE网路径算法详解 https://m.huajiangbk.com/newsview1074077.html
| 上一篇: 版纳三月 柚子花开 |
下一篇: 花柚子とは？本柚子とどう違うのか |
