C++实现多源最短路径之Floyd算法示例

本文实例讲述了C++实现多源最短路径之Floyd算法。分享给大家供大家参考，具体如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX 999
using namespace std;
int n,m;
int e[MAX][MAX];
void Init()
{
  for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
    {
      if(i==j)
        e[i][j]=0;
      else
        e[i][j]=MAX;
    }
}
void Input()
{
  int a,b,c;
  for(int i=1; i<=m; ++i)
  {
    cin>>a>>b>>c;
    e[a][b]=c;
  }
}
void Floyd()
{
  for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
        if(e[i][j]>e[i][k]+e[k][j])
          e[i][j]=e[i][k]+e[k][j];
}
void Output()
{
  for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
      cout<<"dis["<<i<<"]["<<j<<"] = "<<e[i][j]<<endl;
}
int main()
{
  while(1)
  {
    cout<<"n"<<endl;//顶点个数
    cin>>n;
    if(!n) break;
    cout<<"m"<<endl;//边的个数
    cin>>m;
    Init();
    Input();
    Floyd();
    Output();
  }
}

Floyd算法是求多点最短路径的一种算法，其核心代码为

void Floyd()
{
  for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
        if(e[i][j]>e[i][k]+e[k][j])
          e[i][j]=e[i][k]+e[k][j];
}

希望本文所述对大家C++程序设计有所帮助。

赞 (0)

相关推荐

  • c++查询最短路径示例

    c++查询最短路径示例

    复制代码 代码如下: //shortest_path.c#include<stdio.h>#include<stdlib.h>//用file#include<string.h>//可用gets(),puts()#include"shortest_path.h"#define MAX 32767#define MENU "欢迎进入导航系统!\n==========菜单===========\n0.载入北外地图\n1.建立地图\n2.查询最短路

  • C++实现查找二叉树中和为某一值的所有路径的示例

    C++实现查找二叉树中和为某一值的所有路径的示例

    从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径. 打印出和与输入整数相等的所有路径. 例如 输入整数22和如下二元树 则打印出两条路径:10, 12和10, 5, 7. 先序遍历树即可得到结果. 算法: FindPath(BTree * root,int sum,int target,Stack * s) 用来计算,sum为栈中的元素的和,target为目标值. 到达一个节点之后计算当前节点和sum的和,如果为target,输出路径返回,如果大于target,则直接返回,如果小

  • C++用Dijkstra(迪杰斯特拉)算法求最短路径

    C++用Dijkstra(迪杰斯特拉)算法求最短路径

    算法介绍 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低. 算法思想 按路径长度递增次序产生算法: 把顶点集合V分成两组: (1)S:已求出的顶点的集合(初始时只含有源点V0) (2)V-S=T:尚未确定的顶点集合 将T中顶点按递增

  • C++计算图任意两点间的所有路径

    C++计算图任意两点间的所有路径

    基于连通图,邻接矩阵实现的图,非递归实现. 算法思想: 设置两个标志位,①该顶点是否入栈,②与该顶点相邻的顶点是否已经访问. A 将始点标志位①置1,将其入栈 B 查看栈顶节点V在图中,有没有可以到达.且没有入栈.且没有从这个节点V出发访问过的节点 C 如果有,则将找到的这个节点入栈,这个顶点的标志位①置1,V的对应的此顶点的标志位②置1 D 如果没有,V出栈,并且将与v相邻的全部结点设为未访问,即全部的标志位②置0 E 当栈顶元素为终点时,设置终点没有被访问过,即①置0,打印栈中元素,弹出栈顶

  • C++实现多源最短路径之Floyd算法示例

    本文实例讲述了C++实现多源最短路径之Floyd算法.分享给大家供大家参考,具体如下: #include<cstdio> #include<cstring> #include<iostream> #define MAX 999 using namespace std; int n,m; int e[MAX][MAX]; void Init() { for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { if(i==

  • floyd算法实现思路及实例代码

    floyd算法实现思路及实例代码

    正如我们所知道的,Floyd算法用于求最短路径.Floyd算法可以说是Warshall算法的扩展,三个for循环就可以解决问题,所以它的时间复杂度为O(n^3). Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个节点X到B.所以,我们假设Dis(AB)为节点A到节点B的最短路径的距离,对于每一个节点X,我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立,如果成立,证明从A到X再到B的路径比A直接到B的路径短,

  • Java实现Floyd算法求最短路径

    本文实例为大家分享了Java实现Floyd算法求最短路径的具体代码,供大家参考,具体内容如下 import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class TestMainIO { /** * @param args * @throws FileNotFoundException */ public static void main(Stri

  • C语言实现图的最短路径Floyd算法

    C语言实现图的最短路径Floyd算法

    Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径. D代表顶点到顶点的最短路径权值和的矩阵. P代表对应顶点的最小路径的前驱矩阵. 以下程序在DEV C++中调试运行通过. #include <stdio.h> #define INFINITY 65535 typedef int VertexType; //顶点是字符型 typedef int EdgeType; //边是整型 typedef struct //图的邻接矩阵存储结构 { VertexType vexs[9]; /

  • java使用Dijkstra算法实现单源最短路径

    java使用Dijkstra算法实现单源最短路径

    单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径.在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质. 一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的中间顶点,那么P(k,s)必定是从k到s的最短路径.下面证明该性质的正确性. 假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,

  • Java Floyd算法求有权图（非负权）的最短路径并打印

    状态转移方程:d(i,j) = min(d(i,j),d(i,k)+d(k,j)),其中i<k<j 思路对于每一个k(i<k<j),全部遍历下来之后,肯定会发生一次有效的比较 public class FloydTest { private static int[][] matrix; private static int[][] path; public static void main(String[] args) { initMatrixAndPath( new int[][

  • Python基于Floyd算法求解最短路径距离问题实例详解

    本文实例讲述了Python基于Floyd算法求解最短路径距离问题.分享给大家供大家参考,具体如下: Floyd算法和Dijkstra算法,相信大家都不陌生,在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了,今天就用一点时间来重新实现一下,因为本科的时候学习数据结构才开始接触的这个算法,当时唯一会用的就是C语言了,现在的话,C语言几乎已经离我远去了,个人感觉入手机器学习以来python更得我心,因为太通俗易懂了,带给你的体验自然也是非常不错的. 当然网上 有很多的算法讲解教程,我不会在

  • C++求所有顶点之间的最短路径（用Floyd算法）

    C++求所有顶点之间的最短路径（用Floyd算法）

    本文实例为大家分享了C++所有顶点之间最短路径的具体代码,供大家参考,具体内容如下 一.思路: 不能出现负权值的边 用Floyd算法,总的执行时间为O(n的3次方) k从顶点0一直到顶点n-1, 如果,有顶点i到顶点j之间绕过k,使得两顶点间的路径更短,即dist[i][k] + dist[k][j] < dist[i][j],则修改:dist[i][j] 如:(1)当k=0时, 顶点2绕过顶点0到达顶点1,使得路径为:3+1 < dist[2][1],所以,要修改dist[2][1]=4,同

  • java实现Floyd算法

    java实现Floyd算法

    Floyd算法:用于多源最短路径的求解,算出来的是所有的节点到其余各节点之间的最短距离. 该算法的思路是:首先初始化距离矩阵,然后从第一个点开始逐渐更新矩阵点值.d[i][j]表示从i点到j点的距离.第k次更新时,判断d[i][k]+d[k][j]与d[i][j]的大小,如果前者小,则更新这个值,否则不变. 给一个例子: 具体的floyd实现算法如下[java] view plain copy package com.blyang; public class Floyd { int[][] Ma

  • C++的最短路径的弗洛伊德算法案例讲解

    C++的最短路径的弗洛伊德算法案例讲解

    现在我们有这么一张图: 我们要做的是求出从某一点到达任意一点的最短距离,我们先用邻接矩阵来建图,map[i][j]表示从i点到j点的距离,把自己到自己设为0,把自己到不了的边初始化为无穷大,代码为: //初始化 for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(i==j) map[i][j]=0; else map[i][j]=inf; //读入边 for(int i=1; i<=m; i++) { scanf("%d%d%d

随机推荐