文章目录
关键路径：
通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个称为“活动”的子工程。完成了这些“活动”，这个工程就可以完成了。通常用 AOE-网来表示工程。AOE-网是一个带权的有向无环图，其中，顶点表示事件（EVENT），弧表示活动，权表示活动持续的时间。 AOE-网可以用来估算工程的完成时间。可以使人们了解：
（1）研究某个工程至少需要多少时间？
（2）哪些活动是影响工程进度的关键？
由于 AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(Critical Path)。
例：AOE 图如下：
程序执行结束后应该输出：
关键活动为： a1，a4，a7，a10，a8，a11
关 键 路 径 为 ： a1->a4->a7->a10 （ 或 者 V1->V2->V5->V7->V9 ） 和a1->a4->a8->a11（或者 V1->V2->V5->V8->V9）
花费的时间为至少为 ：18（时间单位）。
算法设计：
1、 用邻接表存储一张带权有向图。
2、 对图进行拓扑排序，并进行事件的最早发生时间Ve[i]的计算。
3、 根据排序结果，判断图中是否存在有向环。
4、 根据逆拓扑序列，计算事件的最晚发生时间Vl[i]。
5、 计算活动的最早、最晚发生时间，判断关键活动，找出关键路径。
流程图：
算法实现：
#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef int Boolean;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAX_NAME 5
typedef int InfoType;
typedef char VertexType[MAX_NAME];
/* --------------------------------- 图的邻接表存储表示 --------------------------------*/
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
//表结点
int adjvex; //该弧所指向的顶点的下标
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info; //边权值
}ArcNode;
typedef struct{
VertexType data; //顶点信息
ArcNode *firstarc; //第一个表结点的地址，指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];//邻接表
typedef struct{
//图
AdjList vertices;
int vexnum, arcnum; //顶点数和边数
int kind; //图的种类
}ALGraph;
/* ----------------------------- 需要用的图的邻接表存储的基本操作 --------------------------*/
int LocateVex(ALGraph G, VertexType u){
//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
int i;
for (i = 0; i < G.vexnum; ++i)
if (strcmp(u, G.vertices[i].data) == 0)
return i;
return -1;
}
Status CreateGraph(ALGraph &G){
//创建有向网
int i, j, k;
int w; // 权值
VertexType va, vb;
ArcNode *p;
G.kind = 1;//有向网
printf("请输入图的顶点数和边数(空格隔开): ");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n", G.vexnum, MAX_NAME);
for (i = 0; i < G.vexnum; ++i) {
scanf("%s", G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
for (k = 0; k < G.arcnum; ++k) {
scanf("%d%s%s", &w, va, vb);
i = LocateVex(G, va); // 弧尾
j = LocateVex(G, vb); // 弧头
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->info = (int *)malloc(sizeof(int));
*(p->info) = w;
p->nextarc = G.vertices[i].firstarc; // 插在表头
G.vertices[i].firstarc = p;
}
return OK;
}
void Display(ALGraph G){
// 输出图的邻接表G
int i;
ArcNode *p;
printf("有向图\n");
printf("%d个顶点：\n", G.vexnum);
for (i = 0; i < G.vexnum; ++i)
printf("%s ", G.vertices[i].data);
printf("\n%d条弧(边):\n", G.arcnum);
for (i = 0; i < G.vexnum; i++){
p = G.vertices[i].firstarc;
while (p){
printf("%s→%s :%d", G.vertices[i].data, G.vertices[p->adjvex].data, *(p->info));
p = p->nextarc;
}
printf("\n");
}
}
void FindInDegree(ALGraph G, int indegree[]){
// 求顶点的入度
int i;
ArcNode *p;
for (i = 0; i < G.vexnum; i++)
indegree[i] = 0; /* 赋初值 */
for (i = 0; i < G.vexnum; i++){
p = G.vertices[i].firstarc;
while (p){
indegree[p->adjvex]++;
p = p->nextarc;
}
}
}
typedef int SElemType;
/* ----------------------------------- 栈的顺序存储表示 -----------------------------------*/
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2
typedef struct SqStack{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S){
S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
exit(_OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S){
if (S.top == S.base)
return TRUE;
else
return FALSE;
}
Status GetTop(SqStack s,SElemType &e){
if(s.base==s.top)
return 0;
e = *(s.top - 1);
return 1;
}
Status Push(SqStack &S, SElemType e){
if (S.top - S.base >= S.stacksize) {
S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
if (!S.base)
exit(_OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*(S.top)++ = e;
return OK;
}
Status Pop(SqStack &S, SElemType &e){
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if (S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}
int ve[MAX_VERTEX_NUM], vl[MAX_VERTEX_NUM];//e[]：最早发生时间 vl[]:最迟发生时间
bool flag = 0;
vector<string> path;
int top,down;
void dfs(ALGraph G, int u){
if (G.vertices[u].data == G.vertices[top].data) {
//搜索到终点
if (flag) cout << "\n或者：\n";
cout << G.vertices[down].data; //输出起点
for(auto &it:path) //遍历输出关键路径
cout << it;
flag = 1;
return;
}
ArcNode* p = G.vertices[u].firstarc; //初边
for (; p; p = p->nextarc) {
//遍历
int k = p->adjvex; //该弧所指向的顶点的下标
int dut = *(p->info); //弧的权值
if (ve[u] == vl[k] - dut) {
//是关键活动
path.push_back("->");
path.push_back(G.vertices[k].data); //记录关键活动
dfs(G, k); //继续DFS搜索下一个结点的关键活动
path.pop_back(); //回溯
path.pop_back(); //回溯
}
}
}
//算法7.13
Status TopologicalOrder(ALGraph G, SqStack &T){
int j, k, count, indegree[MAX_VERTEX_NUM],e;
SqStack S;
ArcNode *p;
FindInDegree(G, indegree);
InitStack(S);
for (j = 0; j < G.vexnum; ++j)
if (!indegree[j])
Push(S, j);
GetTop(S, down); //记录起点位置
InitStack(T);
count = 0;
for (j = 0; j < G.vexnum; ++j)
ve[j] = 0; //初始化
while (!StackEmpty(S)){
Pop(S, j);
Push(T, j);
++count; //入栈的顶点数
for (p = G.vertices[j].firstarc; p; p = p->nextarc){
//遍历邻接表
k = p->adjvex; //该弧所指向的顶点的下标
if (--indegree[k] == 0) //入度减为零入栈
Push(S, k);
if (ve[j] + *(p->info) > ve[k])//拓扑正序更新max
ve[k] = ve[j] + *(p->info);
}
}
if (count < G.vexnum){
printf("此有向网有回路\n");
return ERROR;
}
else{
GetTop(T, top);//拓扑排序的最后一个结点为终点
return OK;
}
}
//算法7.14
Status CriticalPath(ALGraph G){
SqStack T;
int i, j, k, ee, el;
ArcNode *p;
char dut, tag;
if (!TopologicalOrder(G, T)) // 产生有向环
return ERROR;
j = ve[0];
for (i = 1; i < G.vexnum; i++) //j=Max(ve[]) 完成点的值
if (ve[i] > j)
j = ve[i];
int maxn = j;
for (i = 0; i < G.vexnum; i++) // 初始化顶点事件的最迟发生时间(最大值)
vl[i] = j; // 完成点的最早发生时间
while (!StackEmpty(T)) // 按拓扑逆序求各顶点的vl值
for (Pop(T, j), p = G.vertices[j].firstarc; p; p = p->nextarc){
k = p->adjvex;
dut = *(p->info); // dut<j,k>
if (vl[k] - dut < vl[j])
vl[j] = vl[k] - dut;
}
printf(" j k dut ee el tag\n");
for (j = 0; j < G.vexnum; ++j)//求ee,el和关键活动
for (p = G.vertices[j].firstarc; p; p = p->nextarc){
k = p->adjvex;
dut = *(p->info);//边权
ee = ve[j];
el = vl[k] - dut;
tag = (ee == el) ? '*' : ' ';
printf("%2d %2d %3d %3d %3d %c\n", j, k, dut, ee, el, tag);
}
printf("关键活动为:\n");
for (j = 0; j < G.vexnum; ++j)
for (p = G.vertices[j].firstarc; p; p = p->nextarc){
k = p->adjvex;
dut = *(p->info);
if (ve[j] == vl[k] - dut)
printf("%s→%s\n", G.vertices[j].data, G.vertices[k].data); // 输出关键活动
}
printf("关键路径为：\n");
dfs(G,0);
printf("\n花费时间最少为：%d\n", maxn);
return OK;
}
int main(){
ALGraph h;
CreateGraph(h);
Display(h);
CriticalPath(h);
}
测试样例：
再加两条：
v1 -> v10(权值为8)
v10 -> v9(权值为10)
测试数据：
请输入图的顶点数和边数(空格隔开): 10 13
请输入10个顶点的值(<5个字符):
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):
6 v1 v2
4 v1 v3
5 v1 v4
1 v2 v5
1 v3 v5
2 v4 v6
9 v5 v7
7 v5 v8
4 v6 v8
2 v7 v9
4 v8 v9
8 v1 v10
10 v10 v9
运行结果
有向图
10个顶点：
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
13条弧(边):
v1→v10 :8v1→v4 :5v1→v3 :4v1→v2 :6
v2→v5 :1
v3→v5 :1
v4→v6 :2
v5→v8 :7v5→v7 :9
v6→v8 :4
v7→v9 :2
v8→v9 :4
v10→v9 :10
j k dut ee el tag
0 9 8 0 0 *
0 3 5 0 3
0 2 4 0 2
0 1 6 0 0 *
1 4 1 6 6 *
2 4 1 4 6
3 5 2 5 8
4 7 7 7 7 *
4 6 9 7 7 *
5 7 4 7 10
6 8 2 16 16 *
7 8 4 14 14 *
9 8 10 8 8 *
关键活动为:
v1→v10
v1→v2
v2→v5
v5→v8
v5→v7
v7→v9
v8→v9
v10→v9
关键路径为：
v1->v10->v9
或者：
v1->v2->v5->v8->v9
或者：
v1->v2->v5->v7->v9
花费时间最少为：18
心得体会
- 在使用邻接表存图过程中再次熟悉链表相关操作。
- 复习栈的编写及使用。利用栈求解拓扑序列。
- 在进行拓扑排序时，掌握结点度（入度）求取，学会拓扑有序的应用：利用拓扑排序进行最早发生时间的计算。
- 复习栈的编写及使用。利用栈存储拓扑有序序列，出栈即得到拓扑逆序序列。并利用拓扑逆序求解最晚发生时间的计算。
- 复习图上深度优先搜索。利用DFS输出关键路径。
参考文献
[1] 严蔚敏，吴伟民.数据结构（C语言版）[M]. 北京：清华大学出版社，1997.4
2021-12-30 更新
1. dfs()起点位置不正确：
错误代码：
dfs(G,0);
正确代码：
dfs(G,down);
0并不是起点的下标，down才是。
例如测试样例改为：
请输入图的顶点数和边数(空格隔开): 9 11
请输入9个顶点的值(<5个字符):
v2 v1 v3 v4 v5 v6 v7 v8 v9
请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):
6 v1 v2
4 v1 v3
5 v1 v4
1 v2 v5
1 v3 v5
2 v4 v6
9 v5 v7
7 v5 v8
4 v6 v8
2 v7 v9
4 v8 v9
dfs(G,0)会输出：
有向图
9个顶点：
v2 v1 v3 v4 v5 v6 v7 v8 v9
11条弧(边):
v2→v5 :1
v1→v4 :5v1→v3 :4v1→v2 :6
v3→v5 :1
v4→v6 :2
v5→v8 :7v5→v7 :9
v6→v8 :4
v7→v9 :2
v8→v9 :4
j k dut ee el tag
0 4 1 6 6 *
1 3 5 0 3
1 2 4 0 2
1 0 6 0 0 *
2 4 1 4 6
3 5 2 5 8
4 7 7 7 7 *
4 6 9 7 7 *
5 7 4 7 10
6 8 2 16 16 *
7 8 4 14 14 *
关键活动为:
v2→v5
v1→v2
v5→v8
v5→v7
v7→v9
v8→v9
关键路径为：
v1->v5->v8->v9 //错误
或者：
v1->v5->v7->v9
花费时间最少为：18
dfs(G,down)会输出：
有向图
9个顶点：
v2 v1 v3 v4 v5 v6 v7 v8 v9
11条弧(边):
v2→v5 :1
v1→v4 :5v1→v3 :4v1→v2 :6
v3→v5 :1
v4→v6 :2
v5→v8 :7v5→v7 :9
v6→v8 :4
v7→v9 :2
v8→v9 :4
j k dut ee el tag
0 4 1 6 6 *
1 3 5 0 3
1 2 4 0 2
1 0 6 0 0 *
2 4 1 4 6
3 5 2 5 8
4 7 7 7 7 *
4 6 9 7 7 *
5 7 4 7 10
6 8 2 16 16 *
7 8 4 14 14 *
关键活动为:
v2→v5
v1→v2
v5→v8
v5→v7
v7→v9
v8→v9
关键路径为：
v1->v2->v5->v8->v9 //正确
或者：
v1->v2->v5->v7->v9
花费时间最少为：18
2. dfs()另一种记录方式：
char* strcmmp(char *a,int n){
char *arr=(char*)malloc(n*sizeof(char));
for(int i=0;i<n-1;i++){
arr[i]=a[i];
}
arr[n-1]='\0';
return arr;
}
void dfs(ALGraph G,int u,char arry[])
{
if(G.adjlist[u].vex==G.adjlist[top].vex)
{
//printf("%s",G.adjlist[down].vex);
for(int i=0;i<strlen(arry);i++)
{
printf("%c",arry[i]);
if(i>=0&&i<strlen(arry)-1)
printf("->");
}
printf("\n");
return ;
}
EdgeNode *p=G.adjlist[u].firstedge;
for(;p;p=p->next)
{
int k=p->adjvex,w=p->weight;
if(etv[u]==ltv[k]-w)
{
//printf("%d\n",k);
arry=strcat(arry,G.adjlist[k].vex);
dfs(G,k,arry);
arry=strcmmp(arry,strlen(arry)-1);
}
}
}
3. C语言完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max_VERTEX_NUM 20
#define ElemType int
#define Status int
#define MAXVEX 100
#define MAX_NAME 5
int top, down;
int *etv, *ltv; //记录事件最早发生时间和最迟发生时间数组
typedef char VertexType[MAX_NAME];
typedef struct nodee //边表节点
{
int adjvex; //邻接点域,存储该顶点对应的下标
int weight; //权值
struct nodee *next; //指向下一个顶点
} EdgeNode;
typedef struct vnode //顶点
{
VertexType vex; //顶点信息
EdgeNode *firstedge; //指向顶点的第一个邻接顶点
} VertexNode, AdjList[Max_VERTEX_NUM];
typedef struct AlGraph
{
AdjList adjlist;
int vexnum; //节点数目
int edgenum; //边的数目
} ALGraph;
//定义一个栈
typedef struct Node
{
ElemType data; //存储数据
struct Node *next; //指向下一个元素
} node, *LinkStackptr;
typedef struct LS
{
LinkStackptr top;
int count; //记录栈中元素的个数
} LinkStack;
Status InitStack(LinkStack *s) //创建一个栈
{
s->top = (LinkStackptr)malloc(sizeof(node));
if (s->top == NULL)
exit(0);
s->top->next = NULL;
s->count = 0;
return 1; //建栈成功返回1
}
Status StackEmpty(LinkStack s) //判断是否为空
{
if (s.count == 0)
return 1; //若栈为空返回1
return 0; //若栈不为空返回 0
}
Status GetTop(LinkStack s, int *e) //返回栈顶元素
{
if (s.top == NULL)
return 0;
*e = s.top->data;
return *e;
}
Status Push(LinkStack *s, ElemType e) //元素入栈(头插）
{
LinkStackptr p = (LinkStackptr)malloc(sizeof(node));
if (p == NULL)
return 0;
p->data = e;
p->next = s->top;
s->top = p; //指向第一个元素的指针
s->count++; //栈中元素个数增加
return 1;
}
Status pop(LinkStack *s, ElemType *e) //返回栈顶元素 ,并删除 (头删)
{
if (s->top == NULL)
return 0;
LinkStackptr p = s->top->next; //指向下一个元素
*e = s->top->data; //将首元素的赋给e
free(s->top);
s->top = p; //删除节点
s->count = s->count - 1; //栈中元素个数减少
return *e; //返回e
}
void CreateALG(ALGraph *ALG, int **indegree) //创建一个图(邻接表存储)
{
printf("请输入节点的数目和边的数目 ");
scanf("%d%d", &ALG->vexnum, &ALG->edgenum);
int i, j, k, w;
EdgeNode *e;
for (i = 0; i < ALG->vexnum; i++)
{
getchar();
// printf("请输入第%d个节点的信息",i+1);
scanf("%s", ALG->adjlist[i].vex); //输入结点信息
ALG->adjlist[i].firstedge = NULL;
}
for (k = 0; k < ALG->edgenum; k++) //边表的建立
{
getchar();
//printf("请输入第%d条边<vi,vj>上的顶点序号和权值",k+1);
scanf("%d%d%d", &w, &i, &j);
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = j - 1;
e->weight = w;
e->next = ALG->adjlist[i - 1].firstedge;
ALG->adjlist[i - 1].firstedge = e; //将结点插入
}
*indegree = (int *)malloc(ALG->vexnum * sizeof(int)); //创建indegree数组求入度
for (i = 0; i < ALG->vexnum; i++)
{
(*indegree)[i] = 0; //(indegree初始化)
}
}
void FindInDegree(ALGraph ALG, int indegree[]) //求各个结点的入度
{
int i;
EdgeNode *temp;
for (i = 0; i < ALG.vexnum; i++) //对每个顶点的边表都进行遍历
{
temp = ALG.adjlist[i].firstedge;
while (temp != NULL)
{
indegree[temp->adjvex]++;
temp = temp->next;
}
}
}
char *strcmmp(char *a, int n)
{
char *arr = (char *)malloc(n * sizeof(char));
for (int i = 0; i < n - 1; i++)
{
arr[i] = a[i];
}
arr[n - 1] = '\0';
return arr;
}
void dfs(ALGraph G, int u, char arry[])
{
if (G.adjlist[u].vex == G.adjlist[top].vex)
{
//printf("%s",G.adjlist[down].vex);
for (int i = 0; i < strlen(arry); i++)
{
printf("%c", arry[i]);
if (i >= 0 && i < strlen(arry) - 1)
printf("->");
}
printf("\n");
return;
}
EdgeNode *p = G.adjlist[u].firstedge;
for (; p; p = p->next)
{
int k = p->adjvex, w = p->weight;
if (etv[u] == ltv[k] - w)
{
//printf("%d\n",k);
arry = strcat(arry, G.adjlist[k].vex);
dfs(G, k, arry);
arry = strcmmp(arry, strlen(arry) - 1);
}
}
}
Status TopologicalSort(ALGraph ALG, int indegree[], LinkStack *T) //拓扑排序
{
int i, count = 0, k;
LinkStack s;
EdgeNode *p;
InitStack(T); //创建一个栈 (用于逆序)
InitStack(&s); //创建一个栈(用于正序）
etv = (int *)malloc(ALG.vexnum * sizeof(int));
for (i = 0; i < ALG.vexnum; i++)
{
etv[i] = 0; // 对记录事件最早发生时间的数组进行初始化
}
for (i = 0; i < ALG.vexnum; i++)
{
if (indegree[i] == 0)
{
Push(&s, i); //遍历找到入度为0的元素入栈
GetTop(s, &down);
}
}
while (!StackEmpty(s)) //循环
{
pop(&s, &i); //出栈
Push(T, i); //入栈
printf("%s ", ALG.adjlist[i].vex); //打印出拓扑正序序列
count++; //记录输出的结点数
for (p = ALG.adjlist[i].firstedge; p; p = p->next)
{
k = p->adjvex;
if (!(--indegree[k])) //出栈的同时对各个结点的入度进行更新
Push(&s, k); //进行判断，若入度为0便入栈
if (etv[i] + p->weight > etv[k]) // 求事件的最早发生时间 //前->后
etv[k] = etv[i] + p->weight;
}
}
if (count < ALG.vexnum) //判断是否有回路
return 0; //若有回路返回0
else
{
GetTop(*T, &top);
return 1;
} //若无回路返回1
}
Status CriticalPath(ALGraph ALG, LinkStack *T, int n) //求关键路径
{
if (n == 0) //判断是否有回路(若有回路程序停止执行)
{
printf("有回路");
return 0;
}
int i, k, w, j;
int ete, lte; //活动的最早，最迟开始时间
EdgeNode *p;
ltv = (int *)malloc(ALG.vexnum * sizeof(int)); //对求事件最迟开始时间的数组进行初始化
j = etv[0];
for (i = 1; i < ALG.vexnum; i++)
{
if (j < etv[i])
j = etv[i];
}
for (i = 0; i < ALG.vexnum; i++)
{
ltv[i] = j; //最后一个事件的最迟开始时间等于其最早开始时间
}
while (!StackEmpty(*T)) //利用拓扑逆序求事件的最迟开始时间
{
pop(T, &i);
for (p = ALG.adjlist[i].firstedge; p; p = p->next)
{
k = p->adjvex;
w = p->weight;
if (ltv[k] - w < ltv[i]) //后->前
ltv[i] = ltv[k] - w;
}
}
for (i = 0; i < ALG.vexnum; i++)
{
for (p = ALG.adjlist[i].firstedge; p; p = p->next)
{
k = p->adjvex;
w = p->weight;
ete = etv[i];
lte = ltv[k] - w; //求活动的最迟开始和最早开始时间
if (ete == lte) //若相等便是关建活动
printf("<%s,%s>length is %d ", ALG.adjlist[i].vex, ALG.adjlist[k].vex, p->weight); //输出关键路径
}
}
printf("\n");
printf("路径长度为： %d", j);
printf("\n");
dfs(ALG, 0, ALG.adjlist[0].vex);
}
int main()
{
ALGraph ALG;
LinkStack T;
int *indegree;
int n;
CreateALG(&ALG, &indegree);
FindInDegree(ALG, indegree);
printf("拓扑正序为:");
n = TopologicalSort(ALG, indegree, &T);
printf("\n");
printf("关键路径为：");
CriticalPath(ALG, &T, n);
}
京公网安备 11010502036488号