必威体育Betway必威体育官网
当前位置:首页 > IT技术

Dijkstra算法

时间:2019-06-28 19:44:29来源:IT技术作者:seo实验室小编阅读:67次「手机版」
 

dijkstra算法

迪杰斯特拉算法可以用来求图的最短路径,本文通过对一个无向图最短路径的求取问题来讲解迪杰斯特拉算法。假如有无向图如下:

首先我们将图按照邻接矩阵的方式存储起来,如果邻接矩阵不是很了解的通过这个链接学习一下:

https://blog.csdn.net/tzm18942553857/article/details/81740995

为了求取图的最短路径,我们要首先建立三个数组P,D,final。P数组中存放用于存储最短路径下标的数组,如P[8]=7表示v0-v8最短路径中,顶点v8的前驱时v7。D数组中用于存放各点最短路径的值。final数组表示如果到顶点v的最短路径已经求取则final[v]=1,若没有求取则final[v]=0。

建立好三个数组后,我们先把与v0顶点有关联的顶点的权值存储到D数组中,然后初始化P数组与final数组为0。首先v0-v0的最短路径为0,则D[v0]=0,此时v0-v0的最短路径已经求得了则final[v0]=1。初始化完成之后D[0]=0,D[1]=1,D[2]=5按照邻接矩阵的存储方式其他的值都为65535。

然后我们在找到从v0出发找到与v0直接相连的顶点的最短路径,此时找到v0-v1是最短路径,将最短路径值赋予min=1,再将final[v1]=1。然后再从v1出发去寻找到一个还未找到最短路径的顶点。找到之后求出通过v1到这个顶点的最短路径。然后将此时的最短路径与D数组中之前存储的最短路径进行比较。采用如下公式进行计算:(min + G.arc[1][2]) < D[2] 。以v2顶点为例,公式中min=1, G.arc[1][2]=3,D[2]=5。找到的一条新的路径为v0-v1-v2的权值和为min + G.arc[1][2]=4小于之前找到的v0-v2这条路径的权值D[2]=5。再将D数组与P数组进行更新:D[2] = min+ G.arc[1][2],P[2] = 1。继续再分析v4顶点,D[4]=65535,min + G.arc[1][4]=6显然D[4],P[4]也要进行更新。将每个顶点更新完成之后。然后再遍历D数组找到最小值将其final数组置1。在此图中为v2,然后再从v2出发寻找与v2相连下一个顶点的最短路径。

在寻找最短路径的过程当中,并不是每条最短路径都是从上一个顶点引申出来的。这句话是什么意思呢?就是我找到了到顶点v5的最短路径,但是到v6的最短路径当中并不包含v5这个顶点。如果将上图中v1-v2的权值改成5,则min + G.arc[1][2]=6,D[2]=5。在D[2]进行更新时其值并不发生改变则到v2的最短路径为v0-v2,到v1的最短路径仍为v0-v1,到v2的最短路径并不包含顶点v1。

代码如下:

#ifndef Graph_H
#define Graph_H
#include<fstream>
#include<iOStream>
#define MAXVEX 100
#define INFINITY 65535
typedef int VertexType;
typedef int EdgeType;
typedef int ShortPathTable[MAXVEX];
typedef int Pathmatirx[MAXVEX];
class Graph
{
public:
	Graph();
	~Graph();
	void CreateMGraph();
public:
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numVertexs, numEdge;
private:

};
#endif 
#include"Graph.h"
using namespace std;
Graph::Graph()
{
}

Graph::~Graph()
{
}
void Graph::CreateMGraph()
{
	int i, j, k, w;
	cout << "输入顶点数和边数" << endl;
	cin >> numVertexs >> numEdge;
	for ( i = 0; i < numVertexs; i++)
	{
		vexs[i]=i;
	}
	ifstream infile;
	infile.open("inputdata.txt");
	for ( i = 0; i < numVertexs; i++)
	{
		for (j = 0;j < numVertexs;j++)
		{
			arc[i][j] = INFINITY;
		}
	}
	for ( k = 0; k < numEdge; k++)
	{
		infile >> i >> j >> w;
		arc[i][j] = w;
		arc[j][i] = w;
	}
	infile.close();
	for (i = 0;i < numVertexs;i++)
	{
		for (j = 0;j < numVertexs;j++)
		{
			cout << arc[i][j] << " ";
		}
		cout << endl;
	}
}
#pragma once
#include"Graph.h"
void dijkstra(Graph& G, int v0, Pathmatirx *p, ShortPathTable *D);
#include "Graph.h"
void Dijkstra(Graph& G,int v0,Pathmatirx *P,ShortPathTable *D)
{
	int v, w, k, min;
	int final[MAXVEX];
	for (int v = 0; v < G.numVertexs; v++)
	{
		final[v] = 0;
		(*D)[v] = G.arc[v0][v];//用于存储到各点最短路径的权值和
		(*P)[v] = 0;//用于存储最短路径的下标值
	}
	(*D)[v0] = 0;
	final[v0] = 1;
	for (v = 1;v < G.numVertexs;v++)
	{
		min = INFINITY;
		for (w = 0;w < G.numVertexs;w++)
		{
			if (!final[w] && (*D)[w] < min)
			{
				k = w;
				min = (*D)[w];
			}
		}
		final[k] = 1;
		for (w = 0;w < G.numVertexs;w++)
		{
			if (!final[w] && (min + G.arc[k][w]) < (*D)[w])
			{
				(*D)[w] = min+G.arc[k][w];
				(*P)[w] = k;
			}
		}
	}
}
#include"Graph.h"
#include"Dijkstra.h"
using namespace std;
void main()
{
	ShortPathTable D;
	Pathmatirx P;
	Graph G;
	G.CreateMGraph();
	Dijkstra(G, 0, &P, &D);
	for (int i = 0;i < G.numVertexs;i++)
	{
		cout << D[i] << " ";
	}
	cout << endl;
	for (int i = 0;i < G.numVertexs;i++)
	{
		cout << P[i] << " ";
	}
	system("pause");
}

代码中为无向图的邻接矩阵的存储,其中inputdata.txt存放着顶点与边的信息,读者可以自己设置。

相关阅读

[图像处理] Sobel边缘检测算法

完成时间:2017/1/23 我的实现结果如下:(图一为原图,图二为边缘检测结果)             关于Sobel算子(英文部分来源于Wikipedia

最小生成树之克鲁斯卡尔算法和普里姆算法

一、最小生成树简介   假设有一个很实际的问题:我们要在n个城市中建立一个通信网络,则连通这n个城市需要布置n-1一条通信线路,这个

遗传算法入门

原文地址为:遗传算法入门优化算法入门系列文章目录(更新中):1. 模拟退火算法2. 遗传算法遗传算法 ( GA , Genetic Algorithm ) ,也称进

图的四种最短路径算法

本文总结了图的几种最短路径算法的实现:深度或广度优先搜索算法,弗洛伊德算法,迪杰斯特拉算法,Bellman-Ford算法1),深度或广度优先搜索

Bilateral Filters(双边滤波算法)原理及实现

双边滤波算法原理: 双边滤波是一种非线性滤波器,它可以达到保持边缘、降噪平滑的效果。和其他滤波原理一样,双边滤波也是采用加权平

分享到:

栏目导航

推荐阅读

热门阅读