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存放着顶点与边的信息，读者可以自己设置。
相关阅读
完成时间：2017/1/23 我的实现结果如下：（图一为原图，图二为边缘检测结果） 关于Sobel算子（英文部分来源于Wikipedia
一、最小生成树简介 假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个
原文地址为：遗传算法入门优化算法入门系列文章目录（更新中）：1. 模拟退火算法2. 遗传算法遗传算法 ( GA , Genetic Algorithm ) ，也称进
本文总结了图的几种最短路径算法的实现：深度或广度优先搜索算法，弗洛伊德算法，迪杰斯特拉算法，Bellman-Ford算法1），深度或广度优先搜索
Bilateral Filters（双边滤波算法）原理及实现
双边滤波算法原理： 双边滤波是一种非线性滤波器，它可以达到保持边缘、降噪平滑的效果。和其他滤波原理一样，双边滤波也是采用加权平