Dijkstra & Floyd 详细可执行代码地址： https://github.com/meihao1203/learning/tree/master/07012018/Graph_Dijkstra_Floyd
迪杰克斯拉(Dijkstra)算法：
按路径长度递增的次序产生最短路径的算法。算法解决了从某个源点到其余各顶点的最短路径问题。求两个顶点之间的最短路径，整个过程都是一步步求起始顶点到相邻顶点的最短路径，直到到达终点。过程中都是基于已经求出的最短路径的基础之上。
| V0→V1 1 V0→V1→V2 4 V0→V1→V2→V4 5 V0→V1→V2→V4→V3 7 V0→V1→V2→V4→V3→V6 10 V0→V1→V2→V4→V3→V6→V7 12 V0→V1→V2→V4→V3→V6→V7→V8 16 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 在求最短路径的过程中，V0到图中所有路径的最短距离都计算过了一遍，只要保存中间结果就可以在求V0→V8的最短路径的同时得到V0到图中任意点的距离 isInShortestPath数组标记对应下标顶点是不是已经计算在最短路径内了 pathPre数组标记对应下标顶点在最短路径的前驱结点是谁，这个结点和weight数组对应，如下表算法开始 weight[3]=∞,这个距离是(0,3)得到的，所以pathPre[3]=0 weight数组标记当前最短路径到对应下标顶点的最短路径，∞就是到不了了 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//算法开始，选中V0顶点开始遍历找最短路径
|
//第一次遍历找到(0,1)，加入顶点1，1可以到达未加入最短路径的顶点2,3,4; 更新数组
//V1->V2 = 4 < 5,更新 依次类推更新weight[3] weight[4]
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//下一次遍历就会选中V2,(1,2),加入顶点2
weight[2]+(2,4)=5
|
//加入weight最小的，且没有加入到最短路径中的顶点4(2,4)
weight[4] = 5,能到达3,5,6,7
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//没加入的3,5,6,7,8中选一条最小权值的边，选择顶点3，（4,3）
weight[3] = 7,3只能到没到过的6,7+(3,6)=10,weight[6]=11,更新
|
//5,6,7,8中选一个weight最小的5
weight[5]=8,5能到为加入最短路径的7 ; weight[5]+(5,7)=13<weight[7],更新
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//没加入的6,7,8中选一个最小的6
weight[6]=10,(6,7)=2,(6,8)=7;
|
//没加入的7,8中选一个最小的7, weight[7]=12
weight[7]=12,(7,8)=4
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//加入最后一个结点8
|
在整个图的遍历搜寻中，从V0顶点到每一个其他顶点的最短距离都在这个过程中保存在weight数组中。 要找到两个点之间的最短路径，只要通过pathPre数组找前驱就好了 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
/* Dijksta.cpp */
#include"Dijkstra.h"
namespace meihao
{
void ShortestPath_Dijkstra(const meihao::Graph& g,int* pathPre,weight_vaule_type* weight,int vertexCnt)
{
if(nullptr==pathPre||nullptr==weight||0==vertexCnt)
return ;
//定义一个数组标记每个结点是否已经在最短路径中
int* isInShortestPath = new int[vertexCnt](); //初始为0，表示都还没有在最短路径之中
//默认从图中第0个结点开始，初始化weight，表示0到其他结点的最短路径
for(int idx=0;idx!=vertexCnt;++idx)
{
weight[idx] = g.getGraphEdgeWeight(0,idx); //weight[idx]存放的就是0到idx的权值
pathPre[idx] = 0; //weight最开始用0到对应下标的距离来初始化，所以pathPre只能全部是0了
}
//计算V0到其他结点的最短路径
isInShortestPath[0] = 1;
for(int idx=1;idx!=vertexCnt;++idx) //V0已经在路径中，只要从下一个顶点开始
{
int min = max_weight_value;
int nextShortestPathVertex = 0; //下一个可以加到最短路径上的顶点
//开始遍历weight数组找到一条从V0顶点到对应数组小标顶点的最有最小权值的边，并记录边的另一端顶点
for(int iidx=0;iidx!=vertexCnt;++iidx)
{
if(0==isInShortestPath[iidx]&&
weight[iidx]<min)
{
nextShortestPathVertex = iidx;
min = weight[iidx];
}
}
//找到了个可以加入到最短路径的顶点
isInShortestPath[nextShortestPathVertex] = 1; //修改nextShortestPathVertex为1
//得到了一个点，通过这个点可以到一些其他顶点，这是后可能路径又会有变化
//加入nextShortestPathVertex，更新weight数组
for(int iiidx=0;iiidx!=vertexCnt;++iiidx)
{
/*if(0==isInShortestPath[iiidx]&&
(weight[nextShortestPathVertex]+g.getGraphEdgeWeight(nextShortestPathVertex,iiidx))<weight[iiidx]) */
//这里错误的原因是有的weigth是weight_vaule_type能表示的最大值，再加就溢出了
if(0==isInShortestPath[iiidx] &&
g.getGraphEdgeWeight(nextShortestPathVertex,iiidx) !=max_weight_value && //多一个条件，防止溢出，也就是(nextShortestPathVertex,iiidx)之间有边的顶点
(weight[nextShortestPathVertex]+g.getGraphEdgeWeight(nextShortestPathVertex,iiidx) ) < weight[iiidx] )
//如果新加入最短路径的点到其他没有标记到最短路径中的点idx的权值小于之前某点到idx的权值，就可以更新这个权值
{
weight[iiidx] = weight[nextShortestPathVertex]+g.getGraphEdgeWeight(nextShortestPathVertex,iiidx);
pathPre[iiidx] = nextShortestPathVertex;
}
}
}
}
void printShortestPath(int vi,int vj,int* pathPre,int vertexCnt)
{
if(nullptr==pathPre||0==vertexCnt||vi<0||vj<0||vi>vj||vi>=vertexCnt||vj>=vertexCnt)
return ;
if(vi==vj)
{
cout<<vi<<" ";
return ;
}
printShortestPath(vi,pathPre[vj],pathPre,vertexCnt);
cout<<vj<<" ";
}
};
|
/* Dijkstra.h */
#ifndef __DIJKSTRA_H__
#define __DIJKSTRA_H__
#include"Graph.h"
namespace meihao
{
void ShortestPath_Dijkstra(const meihao::Graph& g,int* pathPre,weight_vaule_type* weight,int vertexCnt); //参数pathPre数组是用来存放计算得到到图中某一点的最短路径前驱
//pathPre[2] = 1,表示V2到V1的最短路径中,V2前面一个点是V1, ...V1->V2...
//weight是存放指定的一个开始遍历的到对应数组小标的点的权值。eg:图中起始的点V0，weight[2] = N,表示V0到V2的最短路径权值和为N
//定义一个函数输出指定两点之间的最短路径和权值和
void printShortestPath(int vi,int vj,int* pathPre,int vertexCnt);
};
#endif
/* testmain.cpp */
#include"Graph.h"
#include<iostream>
#include"Dijkstra.h"
using namespace std;
int main()
{
meihao::Graph g("data.txt");
int vertexCnt = g.getGraphVertexNumber();
int* pathPre = new int[vertexCnt]();
weight_vaule_type* weight = new weight_vaule_type[vertexCnt]();
meihao::ShortestPath_Dijkstra(g,pathPre,weight,vertexCnt);
for(int idx=0;idx!=vertexCnt;++idx)
{
meihao::printShortestPath(0,idx,pathPre,vertexCnt);
cout<<"路径权值："<<weight[idx];
cout<<endl;
}
cout<<endl;
cout<<"图的起始顶点0到终点8的最短路径：";
meihao::printShortestPath(0,8,pathPre,vertexCnt);
cout<<" 路径权值："<<weight[8]<<endl;
delete []pathPre;
delete []weight;
system("pause");
}
/* data.txt */
9
0 1 2 3 4 5 6 7 8
0 1 5 -1 -1 -1 -1 -1 -1
1 0 3 7 5 -1 -1 -1 -1
5 3 0 -1 1 7 -1 -1 -1
-1 7 -1 0 2 -1 3 -1 -1
-1 5 1 2 0 3 6 9 -1
-1 -1 7 -1 3 0 -1 5 -1
-1 -1 -1 3 6 -1 0 2 7
-1 -1 -1 -1 9 5 2 0 4
-1 -1 -1 -1 -1 -1 7 4 0
|
弗洛伊德(Floyd)算法:
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。
| 图中D-1矩阵是存放的图的临界矩阵，对应的P-1矩阵是存放对应顶点的前驱顶点矩阵。 eg:p[V1][V0]=0,(V1,V0),只能是0; p[V1][V1]=1,(V1,V1); p[V1][V2]=2,(V1,V2) 这是 初始，现以V0为中间顶点更新两个矩阵： (V1,V0)不变，(V1,V1)不变，(V1,V2)->V1,V0,V2 = 3,之前为5，更新 所以更新两个矩阵，p[V1][V2]=0，表示(V1,V2)最短路径中V2前一个结点是V0,对应的D[V1][V2]=3。这时候的矩阵为P0，D0。 |
|
| //以V0为中间顶点，所有点(Vi,Vj)经过V0求路径，确定是否要更新 //和初始矩阵一样，没有变化 |
|
| //以V1为中间顶点，所有点(Vi,Vj)经过V1求路径，确定是否要更新 //之后的每次更新都是在前面得到的中间结果之上，最终到V8，这时候所有点之间的最短路径就都得到了 |
//最终结果，D矩阵中(Vi,Vj)就是Vi，Vj之间的最短路径 //P矩阵中，P[V0][V8]=1表示V0->V8要先经过V0->V1->...->V8，P[V1][V8]=2 ... P[V8][V8]=8 |
| /* Floyd.h */ #ifndef __FLOYD_H__
#define __FLOYD_H__
#include"Graph.h"
#include<iostream>
namespace meihao
{
void ShortestPath_Floyd(const meihao::Graph& g,weight_vaule_type** weight,int** pathPre);
//weight相当于D数组，pathPre相当于P数组
void printPath(int vi,int vj,int vertexCnt,int** pathPre);
//打印vi到vj的最短路径
};
#endif
/* testmain.cpp */
#include"Graph.h"
#include<iostream>
#include"Floyd.h"
#include<iomanip>
using namespace std;
int main()
{
cout<<"test Floyd:"<<endl;
meihao::Graph g("data.txt");
int vertexCnt = g.getGraphVertexNumber();
int** pathPre = new int*[vertexCnt]();
for(int idx=0;idx!=vertexCnt;++idx)
pathPre[idx] = new int[vertexCnt]();
weight_vaule_type** weight = new weight_vaule_type*[vertexCnt]();
for(int idx=0;idx!=vertexCnt;++idx)
weight[idx] = new weight_vaule_type[vertexCnt];
meihao::ShortestPath_Floyd(g,weight,pathPre);
cout<<"print weight matrix:"<<endl;
for(int idx=0;idx!=vertexCnt;++idx)
{
for(int iidx=0;iidx!=vertexCnt;++iidx)
{
cout<<setw(3)<<weight[idx][iidx]<<" ";
}
cout<<endl;
}
cout<<endl;
cout<<"print pathPre matrix:"<<endl;
for(int idx=0;idx!=vertexCnt;++idx)
{
for(int iidx=0;iidx!=vertexCnt;++iidx)
{
cout<<setw(3)<<pathPre[idx][iidx]<<" ";
}
cout<<endl;
}
cout<<endl;
for(int idx=0;idx!=vertexCnt;++idx)
{
meihao::printPath(0,idx,vertexCnt,pathPre);
cout<<"路径权值: "<<weight[0][idx]<<endl;
}
//释放动态内存
for(int idx=0;idx!=vertexCnt;++idx)
{
delete []pathPre[idx];
pathPre[idx] = nullptr;
delete []weight[idx];
weight[idx] = nullptr;
}
delete []pathPre;
pathPre = nullptr;
delete []weight;
weight = nullptr;
system("pause");
}
|
/* Floyd.cpp */ #include"Floyd.h"
#include<iostream>
namespace meihao
{
void ShortestPath_Floyd(const meihao::Graph& g,weight_vaule_type** weight,int** pathPre)
{
if(nullptr==weight||nullptr==pathPre)
return ;
//读取图中数组初始化weight和pathPre
int vertexCnt = g.getGraphVertexNumber();
for(int idx=0;idx!=vertexCnt;++idx)
{
for(int iidx=0;iidx!=vertexCnt;++iidx)
{
weight[idx][iidx] = g.getGraphEdgeWeight(idx,iidx);
pathPre[idx][iidx] = iidx;
}
}
//开始依次选择中间结点，更新weight和pathPre数组
//中间结点为0时和初始化的矩阵一样
for(int idx=1;idx!=vertexCnt;++idx)
{
for(int v=0;v!=vertexCnt;++v)
{
for(int w=0;w!=vertexCnt;++w)
{
if( (max_weight_value!=weight[v][idx] && max_weight_value!=weight[idx][w]) && //经过中间结点idx，(v,idx)和(idx,w)都不能是最大值，不然下边的相加判断会溢出
//max_weight_value是权值weight_vaule_type所能表示的最大值了，再加就溢出
weight[v][w]>(weight[v][idx] + weight[idx][w]) )
{//更新
weight[v][w] = weight[v][idx] + weight[idx][w];
pathPre[v][w] = pathPre[v][idx]; //pathPre[v][w] = idx,也就是(v,w)要先到达idx，但是(v,idx)不是一步就到达的，也要先经过pathPre[v][idx]
//pathPre[v][w] = idx; //不能写这个，要在前面得到的中间结果的基础之上
}
}
}
}
}
void printPath(int vi,int vj,int vertexCnt,int** pathPre)
{
if(vi<0||vj<0||vertexCnt<=0||nullptr==pathPre)
return ;
if(vi==vj)
{
cout<<vi<<" ";
return ;
}
int max = vi>=vj?vi:vj;
int min = vi<vj?vi:vj;
cout<<min<<" "; //从最小的起始点开始
while(min!=max)
{
cout<<pathPre[min][max]<<" "; //第一个要经过的点
min = pathPre[min][max]; //更新起始顶点
}
}
};
|
