计算机学院0101班吴晴 学号200101183000 -1,2,0,MAX,MAx,10,30} i-1, MAX, 4, 0, MAX, MAX, 10) F-1, MAX, MAX, MAX, 0, MAX, MAX; i-1, MAX, MAX, MAX, 15, 0, MAX) F-1, MAX, MAX, MAX, 4, 10, 0) int PATHN+lI )于存放到目的结点最短路径上最后一个点的位置 int STACKINI ∥利用PAIH函数通过栈操作来求出最短路径序列 bool S[N+l ∥判断改结点是否已进行比较 void SHORTEST PATHS(inty)∥/生成最短路径的贪心算法 t int i, num, u; for(i1; K<=N; i++) S[]=0 DIST[=COSTVJ0 PATHI=V S[v]=1; DSTV]=0 for(num=2; num<=N-1; num++) t u=finding S[u=1; for(i-l; K<=N; i++) if(s[==0 & dist[>DisTu+CoSTu) i DIST[=DIST[u+COSTu][] PATHI=u; int finding ∥找找周围路径最短的结点 float temp=MAX; for(i1; K<=N; i++) if(s[=0) if(DIST[]<temp & dist[!=0) i temp=DIST( eturn() int path (int v, int 1) ∥通过栈反序查找 if(PATHSTACKi-1=v) t STACK[G=PATHSTACKi-1ll计算机学院 0101 班 吴晴 学号:2001011830002 4/5 {-1,2, 0, MAX,MAX,10, 30}, {-1,MAX,4, 0, MAX,MAX,10}, {-1,MAX,MAX,MAX,0, MAX,MAX}, {-1,MAX,MAX,MAX,15, 0, MAX}, {-1,MAX,MAX,MAX,4, 10, 0}}; int PATH[N+1]; //用于存放到目的结点最短路径上最后一个点的位置 int STACK[N]; //利用PATH函数通过栈操作来求出最短路径序列 bool S[N+1]; //判断改结点是否已进行比较 void SHORTEST_PATHS(int v) //生成最短路径的贪心算法 { int i,num,u; for(i=1;i<=N;i++) { S[i]=0; DIST[i]=COST[v][i]; PATH[i]=v; } S[v]=1; DIST[v]=0; for(num=2;num<=N-1;num++) { u=findmin(); S[u]=1; for(i=1;i<=N;i++) if(S[i]==0 && DIST[i] > DIST[u]+COST[u][i]) { DIST[i]=DIST[u]+COST[u][i]; PATH[i]=u; } } } int findmin() //找找周围路径最短的结点 { int i,j; float temp=MAX; for(i=1;i<=N;i++) { if(S[i]==0) if(DIST[i]<temp && DIST[i]!=0) { temp=DIST[i]; j=i; } } return(j); } int path(int v,int i) //通过栈反序查找 { int s=1; if(PATH[STACK[i-1]]!=v) { STACK[i]=PATH[STACK[i-1]];