发布时间 : 星期一 文章算法设计技巧与分析习题参考答案更新完毕开始阅读49e501180408763231126edb6f1aff00bfd57079
8.16 修改Dijkstra算法，使它找出最短路径和它的长度。
1. X={1}; Y←V-{1}; λ[1]←0; pre[1]←0; 2. for y←2 to n
3. if y 相邻于1 then λ[y]←length[1,y] 4. else λ[y]← ∞ 5. end if 6. end for
7. for j←1 to n-1
8. 令y∈Y, 使得λ[y]为最小的 9. X←X∪{y} 10. Y←Y - {y} 11. for 每条边(y,w)
12. if w∈Y and λ[y]+length[y,w]< λ[w] then 13. λ[w] ←λ[y]+length[y,w] 14. pre[w] ← y 14. end if
15. end for 16.end for
输出最短路径
void PrintPath(int node) //输出格式为1→…→node { if (node==1) print(“1”); else {
PrintPath( pre[node] ); //先递归再输出 print(“→”, node); } }
13.2 考虑3着色问题，给出一个算法判断一图G=(V,E)的3着色向量c[1…n]是否是合法的。
输入：图G=(V,E)，向量c[1…n]
输出：flag=true 若合法着色；否则2. for i←1 to n 3. if c[i]≠0 4. for (i,j)∈E
5. if c[j]≠0 and c[j]=c[i] 6. return false; 7. end if 8. end for 9. end if 10. end for 11. return true
flag=false 13.3 考虑3着色问题，给出一个算法判断一图G=(V,E)的3着色向量c[1…k]是否是部分的。
输入：图G=(V,E)，向量c[1…k]
输出：true 若着色是部分的；否则输出false 2. for i←1 to k 3. if c[i]≠0 4. for (i,j)∈E
5. if j≤k and c[j]≠0 and c[j]=c[i] 6. return false; 7. end if 8. end for 9. end if 10. end for 11. return true