代價最小演算法
㈠ dijkstra演算法是什麼
迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。
對於圖G=（V，E），將圖中的頂點分成兩組：第一組S：已求出的最短路徑的終點集合（開始為｛v0}）。第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。
堆優化
思考
該演算法復雜度為n^2,我們可以發現，如果邊數遠小於n^2,對此可以考慮用堆這種數據結構進行優化，取出最短路徑的復雜度降為O(1)；每次調整的復雜度降為O（elogn）；e為該點的邊數，所以復雜度降為O((m+n)logn)。
實現
1、將源點加入堆，並調整堆。
2、選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。
3、處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點
1):若該點在堆里，更新距離，並調整該元素在堆中的位置。
2):若該點不在堆里，加入堆，更新堆。
4、若取到的u為終點，結束演算法；否則重復步驟2、3。
㈡ 在N個城市之間鋪設煤氣管道,只需架設N-1條線路即可,如何以最低的經濟代價鋪設.(普里姆演算法)
此題可以用最小生成樹的辦法解決即普里姆如納演算法:把N個城市看作N個頂點,把可以鋪設管道的兩個城市間用線連起來,把相連的兩個城市之間的距離作為這一條邊的權(假設所有管道的單位造價相同).把所有邊的權按照大小排列起來,先選權最小的邊的兩個頂點納入集合S,再選第二條邊,把與這條邊關聯的頂點納入S,但前提是所選的邊不能與前面所選的邊構成迴路,就這樣依次選取.若有權相同的n條邊則任選一條,但前提是所選的邊不能與前面所選的邊構成迴路.接下來選的時候還是選n條邊中的一條前提依然和前面相同.當所粗察選的路的岩橡茄個數為N-1時就停止.此時的線路即為最優的鋪設線路.
㈢ A*演算法——啟發式路徑搜索
A*是一種路徑搜索演算法，比如為游戲中的角色規劃行動路徑。
A* 演算法的輸入是， 起點（初始狀態） 和 終點（目標狀態） ，以及兩點間 所有可能的路徑 ，以及涉及到的 中間節點（中間狀態） ，每兩個節點間的路徑的 代價 。
一般還需要某種 啟發函數 ，即從任意節點到終點的近似代價，啟發函數能夠非常快速的估算出該代價值。
輸出是從 起點到終點的最優路徑 ，即代價最小。同時，好的啟發函數將使得這一搜索運算盡可能高效，即搜索盡量少的節點/可能的路徑。
f(n)=g(n)+h(n)
f(n) 是從初始狀態經由狀態n到目標狀態的代價估計
g(n) 是在狀態空間中從初始狀態到狀態n的實際代價
h(n) 是從狀態n到目標狀態的最佳路徑的估計代價
A*演算法是從起點開始，檢查所有可能的擴展點（它的相鄰點），對每個點計算g+h得到f，在所有可能的擴展點中，選擇f最小的那個點進行擴展，即計算該點的所有可能擴展點的f值，並將這些新的擴展點添加到擴展點列表（open list）。當然，忽略已經在列表中的點、已經考察過的點。
不斷從open list中選擇f值最小的點進行擴展，直到到達目標點（成功找到最優路徑），或者節點用完，路徑搜索失敗。
演算法步驟：
參考
A* 演算法步驟的詳細說明請參考 A*尋路演算法 ，它包含圖文案例清楚的解釋了A*演算法計算步驟的一些細節，本文不再詳細展開。
看一下上面參考文檔中的案例圖，最終搜索完成時，藍色邊框是close list中的節點，綠色邊框是open list中的節點，每個方格中三個數字，左上是f（=g+h），左下是g（已經過路徑的代價），右下是h（估計未經過路徑的代價）。藍色方格始終沿著f值最小的方向搜索前進，避免了對一些不好的路徑（f值較大）的搜索。（圖片來自 A*尋路演算法 ）
現在我們可以理解，A*演算法中啟發函數是最重要的，它有幾種情況：
1) h(n) = 0
一種極端情況，如果h(n)是0，則只有g(n)起作用，此時A*演變成Dijkstra演算法，這保證能找到最短路徑。但效率不高，因為得不到啟發。
2) h(n) < 真實代價
如果h(n)經常都比從n移動到目標的實際代價小（或者相等），則A*保證能找到一條最短路徑。h(n)越小，A*擴展的結點越多，運行就得越慢。越接近Dijkstra演算法。
3) h(n) = 真實代價
如果h(n)精確地等於從n移動到目標的代價，則A*將會僅僅尋找最佳路徑而不擴展別的任何結點，這會運行得非常快。盡管這不可能在所有情況下發生，你仍可以在一些特殊情況下讓它們精確地相等（譯者：指讓h(n)精確地等於實際值）。只要提供完美的信息，A*會運行得很完美，認識這一點很好。
4) h(n) > 真實代價
如果h(n)有時比從n移動到目標的實際代價高，則A*不能保證找到一條最短路徑，但它運行得更快。
5) h(n) >> 真實代價
另一種極端情況，如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS演算法。
關於啟發函數h、Dijkstra演算法、BFS（最佳優先搜索）演算法、路徑規劃情況下啟發函數的選擇、演算法實現時List的數據結構、演算法變種等等更多問題，請參考： A*演算法
㈣ 克魯斯卡爾演算法的演算法描述
克魯斯卡爾演算法的時間復雜度為O（eloge）(e為網中邊的數目)，因此它相對於普里姆演算法而言，適合於求邊稀疏的網的最小生成樹。
克魯斯卡爾演算法從另一途徑求網的最小生成樹。假設連通網N=（V，{E}），則令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=（V，{∮}），圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則捨去此邊而選擇下一條代價最小的邊。依次類推，直至T中所有頂點都在同一連通分量上為止。
例如圖為依照克魯斯卡爾演算法構造一棵最小生成樹的過程。代價分別為1，2，3，4的四條邊由於滿足上述條件，則先後被加入到T中，代價為5的兩條邊（1，4）和（3，4）被捨去。因為它們依附的兩頂點在同一連通分量上，它們若加入T中，則會使T中產生迴路，而下一條代價（=5）最小的邊（2，3）聯結兩個連通分量，則可加入T。因此，構造成一棵最小生成樹。
上述演算法至多對 e條邊各掃描一次，假若以「堆」來存放網中的邊，則每次選擇最小代價的邊僅需O（loge）的時間（第一次需O（e））。又生成樹T的每個連通分量可看成是一個等價類，則構造T加入新的過程類似於求等價類的過程，由此可以以「樹與等價類」中介紹的 mfsettp類型來描述T，使構造T的過程僅需用O（eloge）的時間，由此，克魯斯卡爾演算法的時間復雜度為O（eloge）。
㈤ 根據Prim演算法，求圖示的最小代價生成樹。 設①為起點，要求畫出構造過程。
#include <iostream>
#include <iomanip>
using namespace std;
#define MAX_VERTEX_NUM 10 //最大頂點個數
#define INFINITY 1000 //定義最大值為1000
typedef char VerType;//定點向量
typedef int VRType;//定點之間的關系（即權值）
typedef struct
{
VerType vexs[MAX_VERTEX_NUM]; //頂點向量
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //鄰接矩陣
int vexnum,arcnum; //圖的當前頂點數和弧數
}mgraph, * MGraph;
typedef struct
{
VerType adjvex;
VRType lowcost;
}closedge[MAX_VERTEX_NUM];//記錄從頂點集U到V-U的代價最小的邊的輔助數組定義
//初始化圖
void init_mgraph(MGraph &g)
{
g=(MGraph)malloc(sizeof(mgraph));
g->vexnum=0;
g->arcnum=0;
for(int i=0;i<MAX_VERTEX_NUM;i++)
g->vexs[i]=0;
for(i=0;i<MAX_VERTEX_NUM;i++)
for(int j=0;j<MAX_VERTEX_NUM;j++)
g->arcs[i][j]=INFINITY;
}
void add_vexs(MGraph &g) //增加頂點
{
cout<<"請輸入頂點的個數:"<<endl;
cin>>g->vexnum;
cout<<"請輸入頂點的值"<<endl;
for(int i=0;i<g->vexnum;i++)
{
cin>>g->vexs[i];
}
}
void add_arcs(MGraph &g) //增加邊
{
cout<<"請輸入邊的個數:"<<endl;
cin>>g->arcnum;
VerType ch1,ch2;
巧消int weight;
int row,col;
for(int i=0;i<g->arcnum;i++)
{
cin>>ch1>>ch2>>weight;
for(int j=0;j<g->vexnum;j++)
{
if(g->vexs[j]==ch1)
{
row=j;
}
if(g->vexs[j]==ch2)
{
col=j;
}
}
g->arcs[row][col]=weight; //有向帶權圖只需把1改為weight
g->arcs[col][row]=weight;
}
}
void creat_mgraph(MGraph &g) //創建圖
{
add_vexs(g); //增加頂點
add_arcs(g); //增加邊
}
void print_mgraph(MGraph &g) //列印圖
孝做知胡明{
for(int i=0;i<g->vexnum;i++)
cout<<" "<<g->vexs[i]<<" ";
cout<<endl;
for(i=0;i<g->vexnum;i++)
{
cout<<g->vexs[i];
for(int j=0;j<g->vexnum;j++)
{
cout<<setw(5)<<g->arcs[i][j]<<" ";
}
cout<<endl;
}
}
//返回頂點v在頂點向量中的位置
int LocateVex(MGraph &g, VerType v)
{
int i;
for(i = 0; v != g->vexs[i] && i < g->vexnum; i++)
;
if(i >= g->vexnum)
return -1;
return i;
}
//求出T的下一個節點，第k節點
int minimun(MGraph &g, closedge closedge)
{
int min=INFINITY,k=0,i;
for(i=0;i<g->vexnum;i++)
{
if(closedge[i].lowcost != 0 && closedge[i].lowcost < min)
{
min = closedge[i].lowcost;
k = i;
}
}
return k;
}
//普里姆演算法
void MiniSpanTree_Prim(MGraph &g, VerType u) //普里姆演算法從頂點u出發構造G的最小生成樹T，輸出T的各條邊。
{
closedge closedge;
int i,j;
int k=LocateVex(g,u);
for(j=0;j<g->vexnum;j++) //輔助數組初始化
{
if(j!=k)
{
closedge[j].adjvex=u;
closedge[j].lowcost=g->arcs[k][j];
}
}
closedge[k].lowcost = 0; //初始，U={u}
for(i=1;i<g->vexnum;i++) //選擇其餘g.vexnum-1個頂點
{
k=minimun(g,closedge); //求出T的下一個節點，第k節點
cout<<closedge[k].adjvex<<" "<<g->vexs[k]<<" "<<closedge[k].lowcost<<endl; //輸出生成樹的邊
closedge[k].lowcost=0; //第k頂點並入U集
for(j=0;j<g->vexnum;j++)
{
if(g->arcs[k][j] < closedge[j].lowcost) //新頂點並入集後，選擇新的邊，將小的邊放到輔助數組中
{
closedge[j].adjvex = g->vexs[k];
closedge[j].lowcost = g->arcs[k][j];
}
}
}
}//MiniSpanTree_Prim
int main()
{
MGraph G;
init_mgraph(G); //初始化圖
creat_mgraph(G); //創建圖
print_mgraph(G); //列印圖
MiniSpanTree_Prim(G,G->vexs[0]); //最小生成樹
return 0;
}