#1.算法功能
有向图/无向图中用于计算一个结点到其他所有结点的最短路径.
#2.算法概述
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
#3.算法分析
如图给出无向图:
将上图转换为数据结构(可以用邻接矩阵表示无向图) ,如下:
int data[4][4] = {
{0,1,6,9},
{1,0,MAX,7},
{6,MAX,0,1},
{9,7,1,0}
};
#4.算法代码:
C++代码:
/*
针对无向图的迪杰特斯拉算法
*/
#include
#include
#include
#include
using namespace std;
#define G_MAX 1000 //图的最大值
#define MAX 10000 //无穷大
struct Vertex {
int id;
int d; //初始点到改点的最短路径估计
Vertex *father;//父节点
};
struct Graphy {
int data[G_MAX][G_MAX]; //权值数据
Vertex v[G_MAX];
int num_v;//顶点数
int num_e;//边数
}MyGraphy;
void shortpath_DJ(Graphy &g,Vertex &s) {
//1.初始化
for (int i = 0; i < g.num_v;i++) {
g.v[i].id = i;
g.v[i].d = MAX;
g.v[i].father = NULL;
}
s.d = 0;
//2.处理
//2.1 利用数组和sort构造最小优先级队列
vector S;
vector Q;
for (int i = 0; i < g.num_v;i++) {
Q.push_back(&g.v[i]);
}
for (int i = 0; i < g.num_v;i++) {
Q[g.v[i].id] = &g.v[i];
}
//2.2 处理
while (! Q.empty()) {
Vertex * u = Q[0];
Q.erase(Q.begin());
S.push_back(u);
//2.2.1 对从u出发的边进行松弛操作
for (int i = 0; i < g.num_v;i++) {
int weight_uv = g.data[u->id][g.v[i].id];//u->v 的权重
if (g.v[i].d>u->d+ weight_uv) {
g.v[i].d = u->d + weight_uv;
g.v[i].father = u;
}
}
sort(Q.begin(), Q.end());
}
}
int main() {
//原始数据
int data[4][4] = {
{0,1,6,9},
{1,0,MAX,7},
{6,MAX,0,1},
{9,7,1,0}
};
cin >> MyGraphy.num_v >> MyGraphy.num_e; //结点数,边数
//输入权值信息
for (int i = 0; i < MyGraphy.num_v;i++) {
for (int j = 0; j < MyGraphy.num_v; j++) {
MyGraphy.data[i][j] = data[i][j];
}
}
shortpath_DJ(MyGraphy, MyGraphy.v[0]);
//输出得到的图的结点信息
cout << "起始点到各点的最小路径大小为:" << endl;
for (int i = 0; i < MyGraphy.num_v;i++) {
cout << i <<":"<< MyGraphy.v[i].d << endl;
}
return 0;
}
输入:
4 5
输出结果:
起始点到各点的最小路径大小为:
0:0
1:1
2:6
3:7
参考资料:
《算法导论》
http://blog.csdn.net/longshengguoji/article/details/10756003
http://blog.csdn.net/dodott/article/details/52185222
http://blog.csdn.net/ppp_1026hc/article/details/52106328?locationNum=11
网友评论