構建Dijkstra算法測試圖的策略？

我最近實施Dijkstra算法練習的Java。我現在正在考慮如何構建隨機測試圖（具有單向邊緣）。構建Dijkstra算法測試圖的策略？

目前，我使用了一個天真的方法。節點創建在2d空間中的隨機位置（其中x和y是0和某個MAX_SPACE常量之間的無符號整數）。隨機創建邊緣以連接節點，以便每個節點的出度至少爲1（最多MAX_DEGREE）。不履行不執行。然後，我搜索集合中第一個和最後一個節點之間的路徑，它可能連接也可能不連接。

在更實際的情況中，節點將必須被連接正比於它們在二維空間接近度的概率。用該屬性構建隨機測試圖的好策略是什麼？

注意

我將主要用它來建立一個可以得出並用手驗證圖表，但擴展到更大的圖形是一個考慮因素。

的策略應該很容易修改，以支持以下常數（或者其他人 - 讓我知道，如果你認爲任何有趣的的）：

MIN_NODES，MAX_NODES：爲圖的尺寸範圍
連通性：平均出度
PROXIMITY：體重給予寧願連接近端節點

來源

2012-03-12 theazureshadow

也許[GTgraph（http://www.cse.psu.edu/~madduri/software/GTgraph/index.html）工具可以對你有所幫助。它被用於在最短路徑挑戰下生成圖。另外我發現[this]（http://videolectures.net/ecmlpkdd09_akoglu_rtg/）視頻。 – MadChuckle 2012-03-12 21:39:56

@MadChuckle：那兩個看起來都很有前途。謝謝！ – theazureshadow 2012-03-12 21:50:53

@amit：是的，因爲羣集是許多真實世界情況的特徵。但我不希望任何答案包含*所有*功能。 – theazureshadow 2012-03-12 21:54:17

你可以通過看不同的隨機啓動在JUNG（Java庫）提供圖形發生器：

Barabasi Albert Generator - 簡單的進化無標度隨機圖生成器。在每個時間步驟中，新的頂點被創建，並根據「優先連接」的原則，由此，以更高的程度頂點具有被選擇用於連接的較高概率連接至現有的頂點。
Eppstein Power Law Generator - 圖形發生器，生成與冪律度分佈無向圖。

有可用各種其他發電機 - See Listing Here

對於蟒蛇存在NetworkX庫，還提供了許多圖形發生器 - Listed Here

由於許多這些發電機可以指定大小，所以你可以從小處着手並從那裏出發。

來源

2012-03-23 04:07:08

所有鏈接都被打破。 – 2016-11-18 14:48:52

謝謝你讓我知道@SimonFeatherstone。現在都應該修好了。 – 2016-11-18 14:59:08

構建Dijkstra算法測試圖的策略？

回答

相關問題