文档章节

最短路径Dijkstra算法实现和Floyd算法实现

Bovinitwo
 Bovinitwo
发布于 2016/04/05 21:07
字数 614
阅读 133
收藏 6
/*
Dijkstra算方法(时间复杂度O(n^3))
此程序实现由无向图找到源v0到其他节点的最短路径
*/
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
#define Member 9        
#define MAXINT 65535
typedef int shortpath_weight[Member];       //储存V0到各个节点的最短路径的权重和
typedef int shortpath_pre[Member];          //存储最短路径的前驱,如shortpath_pre[1]=5;就表示v0到v1的最短路径中,v1的前驱是v5
void shortest_Dijkstra(Mgraph G,int v0,shortpath_weight *D,shortpath_pre *P)
{
    int final[Member];//用final记录一个是否已找到v0到这个节点的最短路径
    int i=0,j=0,k=0;
//初始化
    for(i=0;i<G.Nodenum;++i)
    {
        final[i]=0;
        (*D)=G.matrix[v0][i];
        (*P)=0;
    }
    (*D)[v0]=0;
    final[v0]=1;
   
//主循环
 for(i=0;i<G.Nodenum-1;++i)
    {
        //找到下一个最短路径节点
        for(j=0;j<G.Nodenum;++j)
        {
            if(!final[j]&&(*D)[j]<min)
            {
                min=(*D)[j];
                k=j;
            }
        }
        final[k]=1;
        //由最新找到的节点,更新V0到未找到的最短路径节权值和,以及这些节点在V0到它们的最短路径的前驱
        for(j=0;j<G.Nodenum;++j)
        {
            if(!final[j]&&(min+G.matrix[k][j])<(*D)[j])
            {
                (*D)[j]=min+G.matrix[j];
                (*P)[j]=k;
            }
        }
    }
}

Floyd算法:找到图中所有节点到其他所有节点的最短路径

思路:由图的矩阵,使任意两个节点都通过节点0,如果(*D)[m][n]>(*D)[m][0]+(*D)[0][n],则更换(*D)[m][n]的值,更换一次矩阵之后,使任意两个节点都通过1(注意此时矩阵已经更新过通过节点0,顾此时的比较相当于,两个节点可以任意通过节点0或者1或者它们的组合的情况下的最短路径值),依次比较通过节点2,3,4.。。。。。最后就是两个节点通过任意节点组合的最短路径

typedef int shortpath_weight[Member][Member]
typedef int shortpath_later[Member][Member]//注意此处用later是因为,此时的矩阵P[2][5]=3表示的是2到5 的话要先经过3,于是再看p[3][5]=4的话,就是2->3->4->....->5

void ShortestPath_Floyd(Mgraph G,shortpath_weight *D,shortpath_later *P)
{
    int v,w,k;
    //初始化
    for(v=0;v<G.Nodenum;++v)
    {
        for(w=0;w<G.Nodenum;++w)
        {
            (*D)[v][w]=G.matrix[v][w];
            (*P)[v][w]=w;
        }
    }
    //计算最短路径以及路径矩阵
    for(k=0;k<G.Nodenum;++k)
    {
        for(v=0;v<G.Nodenum;++v)
            {
                for(w=0;w<G.Nodenum;++w)
                {
                    if((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
                    {
                        (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
                        (*P)[v][w]=(*D)[v][k];
                    }
                }
            }
    }
}

© 著作权归作者所有

上一篇: Try catch使用模板
下一篇: String类
Bovinitwo
粉丝 1
博文 24
码字总数 12120
作品 0
海淀
程序员
私信 提问
Johnson 全源最短路径算法

前言 上一篇文章已经阐述了Floyd-Warshall算法,适用于存在负权重路径的稠密图。本文讲述的算法适用于稀疏图。 全源最短路径求解其实是单源最短路径的推广,求解单源最短路径的两种算法时间复...

某昆
2017/12/15
0
0
最短路径-Dijkstra算法和Floyd算法

Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dij...

pointerException
2015/08/07
418
0
Dijkstra算法--单源最短路径

在http://blog.csdn.net/hackerzhidian/article/details/54898064这一篇博客中总结了一下在求图的最短路中的一个算法-Floyd算法,Floyd算法用于求图的多源最短路径(多源最短路径:图的所有顶...

Hacker_ZhiDian
2017/02/07
0
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
992
0
最短路径算法

单源最短路径问题 问题描述:给你一个顶点做源点,你想要知道,如何从源点到达其他所有点的最短路径。 OK,这个问题看起来没什么用。我们一般想知道的是A点到B点的最短路径,这个单源最短路径...

Hosee
2016/01/14
3.3K
1

没有更多内容

加载失败,请刷新页面

加载更多

哪些情况下适合使用云服务器?

我们一直在说云服务器价格适中,具备弹性扩展机制,适合部署中小规模的网站或应用。那么云服务器到底适用于哪些情况呢?如果您需要经常原始计算能力,那么使用独立服务器就能满足需求,因为他...

云漫网络Ruan
今天
5
0
Java 中的 String 有没有长度限制

转载: https://juejin.im/post/5d53653f5188257315539f9a String是Java中很重要的一个数据类型,除了基本数据类型以外,String是被使用的最广泛的了,但是,关于String,其实还是有很多东西...

低至一折起
今天
17
0
OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
11
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
9
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部