推 FRAXIS:Floyd演算法只能找最小的路徑 我不懂你要找甚麼 03/11 17:16
※ 引述《FRAXIS (喔喔)》之銘言：
: ※ 引述《gsrr (下象棋)》之銘言：
: : http://www2.lib.nctu.edu.tw/n_exam/exam96/cslz/cslz1001.pdf
: : 第6題要求是否存在一組Index相乘 >1
: : 請問應該如何描述該演算法?
: : 謝謝!
: 首先把建立一個矩陣R'[i,j] = -log R[i,j]
: 如果R[i1,i2] * R[i2, i3] ... R[ik,i1] > 1
: 那麼R'[i1.i2] + R'[i2, i3] ... + R'[ik, i1] < 0
: 把R'想像成是adjacency matrix。
: 問題就轉化成在圖找一個negative cycle，用Bellman-Ford演算法解。
如果我用floyd-warshall algorithm
在判斷A[i,i]上的值,是否有相同效果.
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.195.21