問答題

【簡答題】
已知圖的鄰接矩陣：

（1）按照每對結點間的最短路徑算法ALL-PATH，求每對結點間的最短路徑長度矩陣A⁴。
（2）求路徑結點矩陣P。P（i，j）表示從i到j的最短路徑的第一步結點。
（3）根據(jù)P和A⁴，分別給出結點2到結點4，結點1到結點3的最短路徑及長度。

答案：

你可能感興趣的試題

【簡答題】修改過程ALL_PATHS，使其輸出每對結點（i，j）間的最短路徑，這個新算法的時間和空間復雜度是多少？

答案：

【簡答題】證明對于滿足nmod（k-1）=1的正整數(shù)n，存在一棵具有n個外部節(jié)點的k元樹T（在一棵k元樹中，每個節(jié)點的度至多為k）。進而證明T中所有內(nèi)部節(jié)點的度為k。

答案：當n=1時，存在外部結點數(shù)目為1的k元樹T，并且T中內(nèi)部結點的度為k；
假設當n≤m，且滿足nmod（k...