本文主要向大家介绍了C语言数据结构之Floyd和Dijstra实现最短路径教程，通过具体的内容向大家展示，希望对大家学习C语言有所帮助。

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

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; 

}

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！