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]));
}
}
}
}