C数据结构之Floyd和Dijstra实现最短路径教程

最短路径问题即寻找图中某两个特定结点间的最短的路径长度。

floyd算法：若edge[i][j]表示从节点i到节点j，中间只能经过编号小于k的点时的最短路径长度，若edge[i][k]+edge[k][j]的值edge[i][j]相比，若前者较小则该值代表了新情况中从节点i到节点j的最短路径长度，否则新情况中该路径长度不变。在图的邻接矩阵表示法中，edge[i][j]表示由节点i到节点j中间不经过任何节点的最短路径，那么依次允许经过的节点添加节点1、2……直到n，当添加完节点后，该长度为由节点i到节点j的最短路径。

1.输入多组数据，每组第一行两个整数n大街上的路口数， m 表示有几条路

标号为1的路口为起点，标号为n为的是终点。接下来m行每行有3个数a b c

表示路口a路口b之间有一条路，用时c分钟。求到达的最短时间。

输入样例

2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

样例输出 3 2

#include<stdio.h>  
int ans[101][101]; //二维数组，初值为该图邻接矩阵   
int main()  
{  
    int n,m;  
    while(scanf("%d%d",&n,&m)!=eof)  
    {  
        if(n==0&&m==0) break;  
        for(int i=1;i<=n;i++)  
        {  
            for(int j=1;j<=n;j++)  
            {  
                ans[i][j]=-1;  
            }  
            ans[i][i]=0;  
        }   
        while(m--)  
        {  
        int a,b,c;  
        scanf("%d%d%d",&a,&b,&c);  
        ans[a][b]=ans[b][a]=c; //邻接矩阵赋值，无向图   
        }  
        for(int k=1;k<=n;k++) //k 从1循环到 n ，依次表示允许经过的中间节点编号小于k   
        {  
            for(int i=1;i<=n;i++)//遍历所有ans[i][j]   
            {  
                for(int j=1;j<=n;j++)  
                {  
                  if(ans[i][k]==-1||ans[k][j]==-1) continue;//若两值有一个为负，则ans不能通过k被更新 ，通过k两者不联通   
                  if(ans[i][j]==-1||ans[i][k]+ans[k][j]<ans[i][j])//若有更短路径，则更新   
                  ans[i][j]=ans[i][k]+ans[k][j];  
                }  
            }  
        }  
        printf("%d\n",ans[1][n]);  
    }  
    return 0;  
  
}  

floyd算法时间复杂度n3 被求解数不超过200个节点，邻接矩阵比较方便，若原图不是邻接矩阵，则转换。两个节点间有多余一边的话，选择权值最短的边。适合用于多个节点对之间最短路径长度问题，即全源最短路径问题

//dijkstra算法：

1.初始化，集合k中加入节点1，节点1到节点1的距离为0，到其他节点为无穷

2.遍历与集合k中节点直接相邻的边(u,v,c)其中u属于集合k，v不属于。计算由节点1出发按照已经得到的最短路径到达u，再由u经过该边到达v时的最短路径。比较所有与集合k中节点直接相邻的非集合k节点该路径长度，其中路径最小的节点被确定为下一个最短路径确定的结点，其最短路径即为这个路径长度，最后将这个节点并入集合k。

3.若集合k中已经包含所有点算法结束，否则重复步骤2。

#include<stdio.h>  
#include<vector>  
using namespace std;  
struct e  
{  
    int next;  
    int c;  
};  
vector<e> edge[101];  
bool mark[101];//当mark为true时表示节点j的最短路径已经达到，该节点已加入集合k（完成节点）   
int dis[101]; //mark为ture达到最短路径，否则表示从节点1开始 经过已知的最短路径达到集合k中  
//某节点，在经过另一边到达节点i的路径中最短距离   
int main()  
{  
    int m,n;  
    while(scanf("%d%d",&n,&m)!=eof)  
    {  
        if(n==0&&m==0) break;  
        for(int i=1;i<=n;i++) edge[i].clear();  
        while(m--)  
        {  
            int a,b,c;  
            scanf("%d%d%d",&a,&b,&c);  
            e tmp;  
            tmp.c=c;  
            tmp.next=b;  
            edge[a].push_back(tmp);  
            tmp.next=a;  
            edge[b].push_back(tmp);//将邻接信息加入链表，无向图所以加两次   
        }  
        for(int i=1;i<=n;i++)  
        {  
            dis[i]=-1;  
            mark[i]=false;  
        }  
        dis[1]=0;//得到最近的节点1，长度为0，加入集合k   
        mark[1]=true;  
        int newp=1;  
        for(int i=1;i<n;i++)//循环n-1次 按最短路径递增的顺序确定n-1个点的最短路径长度   
        {  
            for(int j=0;j<edge[i].size();j++) //遍历新加入集合k的点的直接相邻的边   
            {  
                int t=edge[newp][j].next;//该边另一个节点   
                int c=edge[newp][j].c;  
                if(mark[t]==true)  continue; //若该点属于集合k，跳过   
                if(dis[t]=-1||dis[t]>dis[newp]+c)  
                  dis[t]=dis[newp]+c;  
            }  
            int min=999999999;  
            for(int j=1;j<=n;j++)  
            {  
                if(mark[j]==true)  continue;  
                if(dis[j]==-1) continue;  
                if(dis[j]<min)  
                { //若该节点经由点1到k中某个点在经过1条边到达时距离小于当前最小值，更新其为最小值   
                    min=dis[j];  
                    newp=j;//新加入的点暂定为该点  
                }  
            }  
            mark[newp]=true;//将新加入的点加入集合k，dis[newp]虽然数值不变，但意义改变，由所有经过集合k中的结点再  
        }                       //经过一条边到达时的距离中的最小值变为结点1到结点newp的最短距离  
        printf("%d\n",dis[n]);  
    }  
    return 0;  
}