用DijksTra算法找最短路

基于SDN的最短路径算法（dijkstra）实现

一.实验要求

把路由算法作为APP加入到控制器中，使SDN网络实现根据拓扑情况自动选择路由的功能。

二.实验环境及思路

本实验的控制器采用Floodlight，向Floodlight添加模块zhlruote以实现控制器路由功能。

将上题中采用的dijkstra最短路径算法加入到控制器中，控制器根据选择出的路由下发流表给交换机，从而使主机节点能够相互通信。实验中各个链路的带宽约束及带宽需求bdw通过zhlroute模块在init()方法中读取input.txt文件获得，源节点与目的节点通过packetin消息获得。

zhlroute模块初始化完成后，监听PacketIn消息，收到消息后进行判断，如果需要转发，则通过returnRoute（）方法获取目的节点到源节点的完整路径，并对路径上的节点进行遍历以下发流表。在获取路由路径时，使用

floodlight提供的拓扑管理模块（TopologyManager.java）来获取各链路的连接状态（包括连接节点及端口，存储于clusters类集中），通过对各个节点上与其相连的链路的遍历来获取源节点到目的节点的完整路径。

模块整体流程图如图1所示：

1

图1：

基于SDN的最短路径算法（dijkstra）实现

一.实验要求

把路由算法作为APP加入到控制器中，使SDN网络实现根据拓扑情况自动选择路由的功能。

二.实验环境及思路

本实验的控制器采用Floodlight，向Floodlight添加模块zhlruote以实现控制器路由功能。

将上题中采用的dijkstra最短路径算法加入到控制器中，控制器根据选择出的路由下发流表给交换机，从而使主机节点能够相互通信。实验中各个链路的带宽约束及带宽需求bdw通过zhlroute模块在init()方法中读取input.txt文件获得，源节点与目的节点通过packetin消息获得。

zhlroute模块初始化完成后，监听PacketIn消息，收到消息后进行判断，如果需要转发，则通过returnRoute（）方法获取目的节点到源节点的完整路径，并对路径上的节点进行遍历以下发流表。在获取路由路径时，使用

floodlight提供的拓扑管理模块（TopologyManager.java）来获取各链路的连接状态（包括连接节点及端口，存储于clusters类集中），通过对各个节点上与其相连的链路的遍历来获取源节点到目的节点的完整路径。

模块整体流程图如图1所示：

1

图1：

Dijkstra最短路径算法的一种高效率实现

第24卷第3期武汉测绘科技大学学报Vol.24No.3

1999年9月　JournalofWuhanTechnicalUniversityofSurveyingandMappingSept.　1999

3

Dijkstra最短路径算法的一种高效率实现

乐　阳　龚健雅

(武汉测绘科技大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079)

摘　要　在已存在的一些最短路径算法测试总结的基础上,根据GIS中网络计算的实际情况,从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手,提出了一种Dijkstra最短路径算法的高效率实现方法。

关键词　最短路径算法;网络分析;地理信息系统分类号　P208;O22

　　随着计算机的普及以及地理信息科学的发展,GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。相应地,最短路径问题就

2006年全国信息学冬令营讲座

最短路算法及其应用

广东北江中学 余远铭

【摘要】

最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围，并对其应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结。

【关键字】

最短路

【目录】

一、基本概念 .................................................................................... 2

1．1 定义 ................................................................................................................................ 2 1．2简单变体 ...............................................................................

效果展示：

开头输入的是点的序列号（表示第几个点），显示的是最短路径的走法（同样以点的序列号显示，表示途径的第几个点）。

%编写m文件

function [distance,path]=dijkstra(A,s,e) % [DISTANCE,PATH]=DIJKSTRA(A,S,E)

% returns the distance and path between the start node and the end node. %

% A: adjcent matrix % s: start node % e: end node

% initialize

n=size(A,1); % node number

D=A(s,:); % distance vector path=[]; % path vector visit=ones(1,n); % node visibility

visit(s)=0; % source node is unvisible parent=zeros(1,n); % parent node

% the shortest distan

*最长路

function [l,t]=dijkstra_long(A,v) n=length(A); V=1:n; s=v; l=A(v,:);

t=v.*ones(1,n);

ss=setdiff(V,s);nn=length(ss); for j=1:n-1 k=ss(1); for i=1:nn

if l(k)

s=union(s,k); ss=setdiff(V,s); nn=length(ss); end

if length(s)==n break; else

for i=1:nn

if l(ss(i))==inf l(ss(i))=0; end

for m=1:nn

if l(ss(i))

if l(ss(i))

最短路

function [l,t]=dijkstra1(A,v)

%dijkstra最短路算法,某个顶点v到其余顶点

求最短路径的新算法

　CN4321258/TP　ISSN10072130X

　　　　计算机工程与科学

COMPUTERENGINEERING&SCIENCE

2006年第28卷第2期　

　Vol128,No12,2006　

文章编号:10072130X(2006)0220083203

求最短路径的新算法

3

TheNewAlgorithmforFindingtheShortestPaths

徐凤生

XUFeng2sheng

(德州学院计算机系,山东(DepartmentofComputerScienceandTechnology摘　要:,并用。实验表明,该算法能高效Abstract:Anewtheshortestpathshasbeenputforwardinthispaper.Alltheshortestpathsfromonenodetoalltheothernodescanbederivedquicklybyusingthealgorithm.ThealgorithmisverifiedandimplementedbyarelevantCprogram.

关键词:最短路径;Dijkstra算法;邻接矩阵

Keywords:shortestpath;Dijk

本例以由拓扑关系的arc/info 文件为数据源。其中a1,b1,c1是以fnode排序生成的数组，a1对应fnode,b1对应tnode,c1对应length,同样a2,b2,c2,是以tnode 生成的数组。Indexa1是对应某一起点

与其相连的终点的个数，indexb1时对应某一终点与其相连的起点的个数，即其拓扑关系。

Public Function shortpath(startno As Integer, endno As Integer) As Single

以开始点，结束点为参数。 Dim result() As Single Dim result1 As Integer

定义结果点 Dim s1 As Single Dim min As Single Dim ii, I, j, aa As Integer Dim yc() As Boolean Dim ycd() As Boolean Dim rs1() As Single Dim no() As Integer Dim nopoint As Integer ReDim yc(1 To maxno) As Boolean ReDim ycd(1 To maxno) As Bo

本例以由拓扑关系的arc/info 文件为数据源。其中a1,b1,c1是以fnode排序生成的数组，a1对应fnode,b1对应tnode,c1对应length,同样a2,b2,c2,是以tnode 生成的数组。Indexa1是对应某一起点

与其相连的终点的个数，indexb1时对应某一终点与其相连的起点的个数，即其拓扑关系。

Public Function shortpath(startno As Integer, endno As Integer) As Single

以开始点，结束点为参数。 Dim result() As Single Dim result1 As Integer

定义结果点 Dim s1 As Single Dim min As Single Dim ii, I, j, aa As Integer Dim yc() As Boolean Dim ycd() As Boolean Dim rs1() As Single Dim no() As Integer Dim nopoint As Integer ReDim yc(1 To maxno) As Boolean ReDim ycd(1 To maxno) As Bo

#include \#include #include #include

using namespace std;

const int N = 5; const int M = 1000; ifstream fin(\

template

void Dijkstra(int n,int v,Type dist[],int prev[],Type c[][N+1]);

void Traceback(int v,int i,int prev[]);//输出最短路径 v源点，i终点

int main() {

int v = 1;//源点为1

int dist[N+1],prev[N+1],c[N+1][N+1];

cout<<\有向图权的矩阵为：\ for(int i=1; i<=N; i++) {

for(int j=1; j<=N; j++) {

fin>>c[i][j]; cout<

cout<

Dijkstra(N,v,dist,prev,c);

for(int i=2; i<=N; i++) {

cout<<\源点1到点\的最短路径长度为:\，其路径为\ Traceback(1,i,prev); cout<

return 0; }

template

void