最短路径

迪杰斯特拉算法

Dijkstra

单源最短路径问题的最有效的方法

某点到其余各点的最小距离最小路径 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 组织扩充模型,挑选关系最好近的人成为新成员，关系最近的人成为新成员，新成员的关系网纳入发展对象,并更新已经是发展对象的人的关系距离。

弗洛伊德算法

Floyd

//维护A[node_num][node_num]和Path[node_num][node_num]
loop(node_num){
    A[i][j] = min(A[i][j],A[i][mid]+A[mid][j]);
    if(change)Path[i][j]=mid;
        };
1. prim算法过程：prim算法是最小生成树算法，它运用的是贪心原理，设置两个点集合，一个集合为要求的生成树的点集合A，另一个集合为未加入生成树的点B。

  1. 所有的点都在集合B中，A集合为空。(memset(visited,0,sizeof(visited)))

  2. 任意以一个点为开始，把这个初始点加入集合A中，从集合B中减去这个点(visited[1]=1)。寻找与它相邻的点中路径最短的点，如后把这个点也加入集合A中,从集合B中减去这个点（visited[pos]=1）。

  3. 更新未被访问的节点的dist[]值。

  4. 重复上述过程。一直到所有的点都在A集合中结束。

  5. dijkstra算法过程：

    1. 初始时，S只包含源点v，即S=v。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或（若u不是v的出边邻接点）。
    2. 从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
    3. 以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
    4. 重复步骤（2）和（3）直到所有顶点都包含在S中。

  6. 小总结1. Prim是计算最小生成树的算法，Dijkstra是计算最短路径的算法2. 都是使用贪婪(一个局部最优解也是全局最优解)和线性规划(主问题包含n个子问题，而且其中有重叠的子问题。)，每一步都是选择权值/花费最小的边。