最短路径及图的最小生成树汇总与区别

图的最小生成树

1. Kruskal(克鲁斯卡尔)

• 总结首先按照边的权值进行从小到大排序每次从剩余的边中选择权值较小且边的两个顶点不在同一个集合内的边就是不会产生回路的边加入到生成树中直到加入了n-1条边为止。
• Kruskal算法核心代码

  for(i=1;i<=m;i++)//开始从小到大枚举每一条边
   {
      if(merge(e[i].u,e[i].v))//判断一条边的两个顶点是否已经连通即判断是否已在同一个集合中
      {
        count++;//如果目前尚未不连通则选用这条边
        sum=sum+e[i].w;
      }
    if(count==n-1 ) break;//直到选用了n-1条边之后退出循环
    }

1. Prim(普里姆)

• 要用n-1条边将n个顶点连接起来每个顶点都必须至少有一条边与它相连否则这个点就是一个孤立的点。可以随便选一个点开始最终每个点都要被选到看看这个顶点有哪些边与其他顶点相连然后在这些边中找一个最短的边连接另一个顶点。
• 这个方法就像是一棵“生成树”在慢慢长大从一个顶点长到了n个顶点。
• 算法总结将所有的顶点分为两类树顶点已经被选入生成树的顶点和非树顶点还未被选入生成树的顶点。首先选择任意一个顶点加入生成树可以理解为生成树的根。接下来要找出一条边添加到生成树这需要枚举每一个树顶点到每一个非树顶点所有的边然后找到最短边加入到生成树。照此方法重复操作n-1次直到将所有顶点都加入生成树中。
• 代码实现 

#include"stdio.h"
main()
{
    int n,m,i,j,k,min,t1,t2,t3;
    int e[7][7],dis[7],book[7]={0};//用数组book来记录该顶点是否已经加入生成树 
    int inf=99999999;//正无穷 
    int count=0,sum=0;//count用于记录生成树中顶点个数sum用来存储路径之和 
    scanf("%d %d",&n,&m);//n代表顶点个数m代表边数 
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(i==j) e[i][j]=0;//从自己到自己记为0 
    else e[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);//无向图 
        e[t1][t2]=t3;
        e[t2][t1]=t3;
    }
    for(i=1;i<=n;i++)
    dis[i]=e[1][i];//1号顶点到各个顶点的初始距离因为当前生成树中只有1号顶点 
    book[1]=1;
    count++;
    while(count<n)//如果所有顶点都加入了生成树则退出循环 
    {
        min=inf;//找到未加入生成树距离任意已经加入生成树顶点最近的一个顶点 
        for(i=1;i<=n;i++)
        {
            if(book[i]==0&&dis[i]<min)
            {
                min=dis[i];j=i;
            }
        }
        book[j]=1;count++;sum=sum+dis[j];//将找到的顶点加入生成树 
        for(k=1;k<=n;k++)//扫描当前加入的顶点j所有的边再以j为中间点更新生成树到每一个非数顶点的距离 
        {
            if(book[k]==0&&dis[k]>e[j][k])
            dis[k]=e[j][k];
         } 
    }
    printf("%d",sum);//输出最短路径 
} 

Kruskal算法和Prim算法的区别Kruskal算法是一步步将森林中树进行合并而Prim算法则是通过每次增加一条边来建立一棵树。Kruskal按照从小到大的顺序去考察每一条边每次都是先给最小边机会。Prim每次都是选择距离生成树最近的边。这两种算法每一次的选择都是局部最优解。

最短路径

1. Dijkstra(狄克斯特拉)

• 此算法用于指定一个点源点到其余各个顶点的最短路径也叫做“单源最短路径”。
• 算法总结每次找到离源点最近的一个顶点然后以该顶点为中心进行扩展最终得到源点到其余所有点的最短路径。
• 扩展过程中以顶点的边来进行扩展看从源点到这个顶点是否能通过别的点与之相连的边更短如果是的话该点到源点的距离就要更新记录这个过程也称之为“松弛”。
• 算法实现

将所有顶点分成两部分已知最短路径的顶点集合P未知最短路径的顶点集合Q。最开始集合P中只有源点。用一个数组book来记录哪些点已经在集合P中。

将源点s到自己的最短路径设为0即dis[s]=0。若存在源点能直接到达的顶点i则把dis[i]设为e[s][i]。把其他源点不能直接到达的顶点的最短路径设为正无穷。

在集合Q的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小)加入到集合P。并考察所有以点u为起点的边对每一条边进行松弛操作。

重复上一步当集合Q为空算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。

• 代码如下

 

#include"stdio.h"
main()
{
    int e[10][10],dis[10],book[10];
    int i,j,n,m,t1,t2,t3;
    int u,v,min;
    int inf=99999999;
    scanf("%d %d",&n,&m);//n代表顶点数m代表边数
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(i==j) e[i][j]=0;
    else e[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;
     } 
     for(i=1;i<=n;i++)
     dis[i]=e[1][i];
     for(i=1;i<=n;i++)
     book[i]=0;
     book[1]=1;
     //Dijkstra核心语句 
     for(i=1;i<=n-1;i++)
     {
         min=inf;
         for(j=1;j<=n;j++)
         {
             if(book[j]==0&&dis[j]<min)
             {
                 min=dis[j];
                 u=j;
             }
         }
     book[u]=1;
     for(v=1;v<=n;v++)
     {
         if(e[u][v]<inf)
         {
             if(dis[v]>dis[u]+e[u][v])
             dis[v]=dis[u]+e[u][v];
          } 
     }
}
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
}

1. Floyd(弗洛伊德)

• 求任意两点之间的最短路径这个问题也被称为“多源最短路径”问题。
• 通过找到中间节点找出从起点单向到达终点的最短路径。
• Floyd算法又称插点法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。百度
• 代码实现

从任意一条单边路径开始。所有两点之间的距离是边的权如果两点之间没有边相连则权为无穷大。

对于每一对顶点u和v看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果是更新它。

• 代码实现

#include"stdio.h"
main()
{
    int e[10][10],k,i,j,n,m,t1,t2,t3;
    int inf=99999999;
    scanf("%d %d",&n,&m);//n代表顶点个数m代表边数 
    for(i=1;i<=n;i++)//初始化 
    for(j=1;j<=n;j++)
    if(i==j) e[i][j]=0;
    else e[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;//单向 
    }
    //Floyd-Warshall算法核心语句
    for(k=1;k<=n;k++)//允许中转经过的点 
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];
    //输出结果 
    for(i=1;i<=n;i++) 
    {
        for(j=1;j<=n;j++)
        {
            printf("%10d",e[i][j]);
        }
        printf("\n");
    }
}