贪心算法之单源最短路径

问题：在一个有向网络中，从某点出发得到所有到该顶点的最短距离。

迪杰斯特拉算法是解单源最短路径问题的一个贪心算法，其基本思想是，设置顶点集合S不断的贪心选择来扩充这个集合。当源点到该顶点的最短距离已知，则添加到集合来，最终包括网络中的所有顶点。

贪心选择：

step1:首先选择网络中的某一顶点V出发，那么该顶点肯定可以添加到S中，然后以V为源点，得到它到其他顶点的距离（初始化d[]，表示V到其他顶点的距离)

step2:在这些顶点中选择没有标记过的（即未添加到S集合中的点)  并且到V的距离最小的顶点V’，然后将其标记

step3:更新d[],从V'出发遍历网络没有标记的顶点，如果找到一个点d[u]+edge[u][j]

step4:重复step2

性能分析：

      算法时间主要花在两个for循环中，时间复杂度为O（n2)

代码实现：

#include

typedef char VertexType;
typedef int EdgeType;
#define MAX 20//定义数组大小
#define INFINITY 500

typedef struct 
{
VertexType vexs[MAX];
EdgeType edges[MAX][MAX];
int vexnum;//记录图的顶点数
int arcnum;//记录图的边或弧的条数
}AdjMatrix;
//创建图的邻接矩阵
AdjMatrix CreatGraph_Matrix(int graphtype)