http://exam.lib.ncku.edu.tw/showfile.php?file=exam/%E7%A2%A9%E5%A3%AB%E7%8F%AD%E8%80%83%E8%A9%A6/%E9%9B%BB%E6%A9%9F%E8%B3%87%E8%A8%8A%E5%AD%B8%E9%99%A2/%E9%9B%BB%E6%A9%9F%E8%B3%87%E8%A8%8A%E5%AD%B8%E9%99%A2-%E8%B3%87%E8%A8%8A%E8%81%AF%E6%8B%9B/104%E8%B3%87%E8%A8%8A%E5%B7%A5%E7%A8%8B%E5%AD%B8%E7%B3%BB%E3%80%81%E9%86%AB%E5%AD%B8%E8%B3%87%E8%A8%8A%E7%A0%94%E7%A9%B6%E6%89%80%E8%81%AF%E6%8B%9B/209_%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88.pdf
3(a). for(int k=0;k<n;k++)
if(!found[k] && distance[k]<min)
{
min = distance[k];
minpos = k;
}
(b) for(int i=0;i<n;i++)
for(int u=0;u<n;u++)
5. 16375
6.Theta(n^1/2*lgn)
7.有負環所以no solution
這幾題這樣寫不知道對不對 希望會的人指點一下
還有 第四題 不知道怎麼下手QQ
感謝~

4.找拓撲排序,再從與最前的點相連的邊開始依序作bellman algo.中的 relaxdfs找拓撲花O(V+E),而bellman ford只要知道shortest path上邊的正確的relax順序就只需O(E)3.b i,u變數好像要對調比較好, 7,我算似乎有解

7我算好像有負cycle@@ 不確定

7.的確有負cycle,sor3.b 他把k=1的情況在initial時候作了吧

想順便請問一下第七題，這題用負cycle,即可判斷，那v0到各點的最短距離是不是沒求也沒關係，我看解答都有求說，感謝大大

有解給解集用的吧, 配分重時最好也列一下

好的，謝謝你！！