算法设计技巧与分析习题参考答案

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