dij演算法

㈠ 最佳優先搜索演算法（Best-First-Search）

最佳優先搜索演算法是一種啟發式搜索演算法（Heuristic Algorithm），其基於廣度優先搜索演算法，不同點是其依賴於估價函數對將要遍歷的節點進行估價，選擇代價小的節點進行遍歷，直到找到目標點為止。BFS演算法不能保證找到的路徑是一條最短路徑，但是其計算過程相對於Dijkstra演算法會快很多。

n表示當前的點，g(n)為從起始點到點n的實際代價，h(n)為從點n到目標點的估價。

（1）BFS沒有障礙物時的尋路

（2）BFS遇到障礙物時的尋路

結論：
（1）BFS演算法通過估價函數，會將探測快速的導向目標點的方向，其不能夠保證尋找到一條最短路徑的點，但是其搜索的效率上相對於Dijestra演算法會快上很多。
（2）在地圖上有障礙物的情況，BFS尋找的路徑一般都不是最短路徑，在尋路過程中可以嘗試配合其他的方法，對尋路進行修正。

㈡ 層次聚類的兩類方法分別是什麼

層次聚類的兩類方法分別是聚合及分裂。

層次聚類的定義：

層次聚類假設類別之間存在層次結構，層次聚類的目標是將樣本分類聚集到不同層次的類別中。

層次聚類主要有兩種方法：

1.聚合（自下而上）：聚合分類需要預先確定以下三要素：距離或相似度、合並規則、停止條件

2.分裂（自上而下）：分裂分類需要預先確定以下三要素：距離或相似度、分裂規則、停止條件

聚合分類演算法：

輸入：n個樣本組成的樣本集合、聚合分類三要素

輸出：樣本集合的層次化聚類

計算樣本集合中兩兩樣本間的距離，形成距離矩陣D=[dij]n×n

構造n個類，每個類只包含一個樣本；

依據合並規則，判斷樣本類別間距離或相似度是否滿足合並條件，如果滿足則構建一個新類，並將相關的兩個樣本分配到這個新類中，否則判斷當前最新的類別數是否為1（聚合），如果是1，就終止計算；

計算這個新類與其他各類之間的距離或相似度，返回步驟3。

㈢ 來解釋下spfa和Dijkstra的優缺點

DIJ演算法和SPFA演算法優缺點：

DIJ演算法不能解決負權環，但是比SPFA快（特別是+入heap甚至fib heap後，當然當邊數少的時候SPFA比DIJ快）。
SPFA演算法能解決負權環，但是比DIJ慢。

㈣ Floyed演算法，spfa演算法，dij演算法各自的優勢都在哪裡哪個適用於無向圖哪個適用於負權邊急！

直覺感覺是迪傑斯特拉的比較好。。。留個名。

㈤ Dijkstra演算法的C語言實現：文件讀取、圖的存儲、演算法實現、路徑輸出

要現寫，你的分太少了，至少也200分吧，我給你個模板，時間復雜度為nLOG2(n)：
dij鄰接陣
#include <algorithm>
#include <deque>
#include <queue>
#include <iostream>
using namespace std;
#define MN 1001
#define INF (1<<29)
int graf[MN][MN];
struct node
{
int v;
int dis;
node(int vv,int dd){v=vv;dis=dd;}
node(){}

};
bool operator < (const node aa,const node bb)
{
return aa.dis>bb.dis;//最小堆
}
int dis[MN];
void dijkstra(int s,int n)//s是源點,[1..n]
{
node tmp;
int i,w;
for(i=1;i<=n;++i){dis[i]=INF;}
priority_queue < node,deque<node> > Q;
Q.push(node(s,0));
for(dis[s]=0;!Q.empty();)
{
tmp=Q.top();Q.pop();
if(tmp.dis!=dis[tmp.v])continue;
for(i=1;i<=n;++i)
{
w=graf[tmp.v][i];
if(w!=INF&&dis[tmp.v]+w<dis[i])
{
//必要時可保存路徑pre[i]=tmp.v
dis[i]=dis[tmp.v]+w;
Q.push(node(i,dis[i]));
}
}
}
}