经典算法之Dijkstra算法(求图中任意一对顶点间的最短路径)
程序员文章站
2024-03-15 18:54:36
...
/************************
author's email:[email protected]
date:2018.1.30
************************/
/*
迪杰斯特拉算法思想:
设有两个顶点集合S和T,集合S中存放图中已找到最短路径的顶点,集合T存放图中剩余顶点,初始状态时
集合S中只包含源点v0,然后不断从集合T中选取到顶点v0路径长度最短的顶点Vu并入到集合S中。集合S
每并入一个新的顶点Vu,都要修改顶点V0到集合T中顶点的最短路径长度值。不断重复此过程,直到集合T
的顶点全部并入到S中为止。
迪杰斯特拉算法时间复杂度分析:
由算法代码可知,本算法主要部分为一个双重循环,外层循环内部有两个并列的单层循环,可以在取一个
循环内的操作作为基本操作,基本操作执行的总次数即为双重循环执行的次数,为n^2次,因此本算法的
时间复杂度为O(n^2)。
*/
#include<iostream>
#define INF 100//INF为比图中任何权值都大的数
#define maxSize 7 //图的顶点数
#define number 12 //图的边数
using namespace std;
typedef struct {//图的定义
int edges[maxSize][maxSize];//邻接矩阵的定义
int n, e; //分别为顶点数和边数
}MGraph;
MGraph createGraph(MGraph g);
void Dijkstra(MGraph g, int v, int dist[], int path[]);/*迪杰斯特拉算法代码,函数结束时
dist[]存放了v点到其余各顶点的最短路径长度,path[]中保存从V到各顶点的最短路径*/
void printfPath(int path[], int a);//输出起始点v到终点a之间的最短路径
int main() {
MGraph g;//定义并初始化图g
g.edges[maxSize][maxSize] = { 0 };
g.n = maxSize; g.e = number;
g = createGraph(g);//创建一个图
int dist[maxSize] = {0};
int path[maxSize] = {0};
int v = 0;//起始点
Dijkstra(g, v, dist, path);
cout << "顶点"<<v<<"到各顶点的最短路径及最短路径长度为:" << endl;
for (int i = 1; i < maxSize; ++i)
{
printfPath(path, i);
cout<<"最短路径长度为:" << dist[i]<<endl;
}
system("pause");
return 0;
}
MGraph createGraph(MGraph g) {
int i, j;
for (i = 0; i < maxSize; i++)
{
for (j = 0; j < maxSize; j++)
{
g.edges[i][j] = INF;
}
}
g.edges[0][1] = 4;
g.edges[1][0] = 4;
g.edges[0][2] = 6;
g.edges[2][0] = 6;
g.edges[0][3] = 6;
g.edges[3][0] = 6;
g.edges[1][2] = 1;
g.edges[2][1] = 1;
g.edges[1][4] = 7;
g.edges[4][1] = 7;
g.edges[2][3] = 2;
g.edges[3][2] = 2;
g.edges[2][4] = 6;
g.edges[4][2] = 6;
g.edges[2][5] = 4;
g.edges[5][2] = 4;
g.edges[3][5] = 5;
g.edges[5][3] = 5;
g.edges[4][5] = 1;
g.edges[5][4] = 1;
g.edges[4][6] = 6;
g.edges[6][4] = 6;
g.edges[6][5] = 8;
g.edges[5][6] = 8;
g.n = maxSize;
g.e = number;
return g;
}
/*迪杰斯特拉算法代码,函数结束时
dist[]存放了v点到其余各顶点的最短路径长度,path[]中保存从V到各顶点的最短路径*/
void Dijkstra(MGraph g, int v, int dist[], int path[])
{
int set[maxSize];/*set[]为标记数组,set[Vi]=0表示Vi在T中,即没有被并入最短路径;
set[Vi]=1表示Vi在S中,即已经被并入最短路径。*/
int min, i, j, u;
//对各数组初始化
for (i = 0; i < g.n; ++i)
{
dist[i] = g.edges[v][i];
set[i] = 0;
if (g.edges[v][i] < INF)
path[i] = v;
else
path[i] = -1;
}
set[v] = 1; path[v] = -1;//初始化结束
for (i = 0; i < g.n - 1; ++i)
{
min = INF;
/*这个循环每次从剩余顶点中选出一个顶点,通往这个顶点的路径在通往所有剩余顶点的路径中
是长度最短的*/
for (j=0;j<g.n;++j)
{
if (set[j] == 0 && dist[j] < min)
{
u = j;
min = dist[j];
}
}
set[u] = 1;//将选出的顶点并入最短路径中
/*这个循环以刚并入的顶点作为中间点,对所有通往剩余顶点的路径进行检测*/
for (j = 0; j < g.n; ++j)
{
/*这个if语句判断顶点u的加入是否会出现通往顶点j的更短的路径,如果出现,则
改变原来路径及其长度,否则什么都不做。*/
if (set[j] == 0 && dist[u] + g.edges[u][j] < dist[j])
{
dist[j] = dist[u] + g.edges[u][j];
path[j] = u;
}
}
}
}
void printfPath(int path[], int a)//输出起始点v到终点a之间的最短路径
{
int stack[maxSize], top = -1;//定义并初始化栈
/*这个循环以由叶子节点到根节点的顺序将其入栈*/
while (path[a] != -1)
{
stack[++top] = a;
a = path[a];
}
stack[++top] = a;
while (top != -1)
{
cout << stack[top--] << " ";//出栈并打印出栈元素,实现了顶点的逆序打印
}
cout << endl;
}