代价最小算法
㈠ 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;
}