dijstra
dijstra主要使用场景场景注意事项结构模板结构模板主体初始化函数遍历函数
实现cpp
经典问题正权单源最短路问题描述例题演示实现cpp
参考文献
dijstra
主要使用场景场景
计算边权为正的图的单源最短路径
注意事项
边权必须为正dijstra算法的处理对象是图,图可以以各种方式保存,这里采用邻接矩阵的方式这个算法把图和一对节点输入,并把最短路径写在path数组数组里.(path实际保存的是当前节点在最短路径的下一个节点)如果想检测到目的地就停止可以在每次循环的末尾判断destination的邻接节点是否都known==true是则可以结束.
结构
dijstra算法需要三个数组,
vector<bool> known;标记已经考虑过的节点.vector<int> cost;标记这轮比较前的花费,vector<vector<int>> path标记最短路里当前节点的前一个节点,这里可能有多条,因此path采用了vector<vector<int>>的形式保存.
模板
结构模板
主体
主体相对简单包含初始化和遍历两个函数
void dijstra(vector
<vector
<int>> graph
, vector
<vector
<int>> &path
, int departure
, int destination
)
{
int size
= graph
.size();
vector
<bool> known
;
vector
<int> cost
;
initiate(known
, cost
, path
, departure
);
loop(graph
, known
, cost
, path
, destination
);
}
初始化函数
这里需要对用到的三个数组进行初始化,known全标记未知(false)cost全标记最大代表还没有路,path全标记-1代表没有前缀. 同时需要把初始节点的cost变为最小(0);
void initiate(vector
<bool> &known
, vector
<int> &cost
, vector
<vector
<int>> &path
)
{
for (int i
= 0; i
< known
.size(); i
++)
{
known
[i
] = false;
}
for (int i
= 0; i
< cost
.size(); i
++)
{
cost
[i
] = INT_MAX
;
}
for (int i
= 0; i
< path
.size(); i
++)
{
for (int j
= 0; j
< path
[i
].size(); j
++)
{
path
[i
][j
] = NO_PREVERTEX_SIGN
;
}
}
}
遍历函数
其实主要的操作数组是cost,遍历也是以cost的大小进行遍历
每次在cost里找最小标记访问,进行访问,找临边临边的花费如果比本点的花费与本点到临边的路径和大则更新邻接点的costpath,等于则加入parh,小于不做事.
void loop(vector
<vector
<int>> graph
, vector
<bool> &known
, vector
<int> &cost
, vector
<vector
<int>> &path
, int destination
)
{
int size
= graph
.size();
for (int i
= 0; i
< size
; i
++)
{
int minIndex
= INT_MAX
;
for (int i
= 0; i
< cost
.size(); i
++)
{
if (known
[i
] == false && cost
[i
] < minIndex
)
{
minIndex
= i
;
}
}
known
[minIndex
] = true;
for (int j
= 0; j
< graph
[minIndex
].size(); j
++)
{
if (graph
[minIndex
][j
] != 0)
{
if (cost
[j
] > cost
[minIndex
] + graph
[minIndex
][j
])
{
cost
[j
] = cost
[minIndex
] + graph
[minIndex
][j
];
path
[j
].clear();
path
[j
].push_back(minIndex
);
continue;
}
if (cost
[j
] == cost
[minIndex
] + graph
[minIndex
][j
])
{
path
[j
].push_back(minIndex
);
}
}
}
int j
= 0;
for (; j
< graph
[destination
].size(); j
++)
{
if (graph
[destination
][j
] != 0)
{
if (known
[j
] == false)
{
break;
}
}
}
if (j
== graph
[destination
].size())
{
return;
}
}
}
实现
cpp
#include <bits/stdc++.h>
#include <vector>
using namespace std
;
const int vertexSize
= 100;
const int NO_PREVERTEX_SIGN
= -1;
void initiate(vector
<bool> &known
, vector
<int> &cost
, vector
<vector
<int>> &path
, int departure
)
{
for (int i
= 0; i
< known
.size(); i
++)
{
known
[i
] = false;
}
for (int i
= 0; i
< cost
.size(); i
++)
{
cost
[i
] = INT_MAX
;
}
cost
[departure
] = 0;
for (int i
= 0; i
< path
.size(); i
++)
{
for (int j
= 0; j
< path
[i
].size(); j
++)
{
path
[i
][j
] = NO_PREVERTEX_SIGN
;
}
}
}
void loop(vector
<vector
<int>> graph
, vector
<bool> &known
, vector
<int> &cost
, vector
<vector
<int>> &path
, int destination
)
{
int size
= graph
.size();
for (int i
= 0; i
< size
; i
++)
{
int minIndex
= INT_MAX
;
for (int i
= 0; i
< cost
.size(); i
++)
{
if (known
[i
] == false && cost
[i
] < minIndex
)
{
minIndex
= i
;
}
}
known
[minIndex
] = true;
for (int j
= 0; j
< graph
[minIndex
].size(); j
++)
{
if (graph
[minIndex
][j
] != 0)
{
if (cost
[j
] > cost
[minIndex
] + graph
[minIndex
][j
])
{
cost
[j
] = cost
[minIndex
] + graph
[minIndex
][j
];
path
[j
].clear();
path
[j
].push_back(minIndex
);
continue;
}
if (cost
[j
] == cost
[minIndex
] + graph
[minIndex
][j
])
{
path
[j
].push_back(minIndex
);
}
}
}
int j
= 0;
for (; j
< graph
[destination
].size(); j
++)
{
if (graph
[destination
][j
] != 0)
{
if (known
[j
] == false)
{
break;
}
}
}
if (j
== graph
[destination
].size())
{
return;
}
}
}
void dijstra(vector
<vector
<int>> graph
, vector
<vector
<int>> &path
, int departure
, int destination
)
{
int size
= graph
.size();
vector
<bool> known
;
vector
<int> cost
;
initiate(known
, cost
, path
, departure
);
loop(graph
, known
, cost
, path
, destination
);
}
int main(int argc
, char const *argv
[])
{
vector
<vector
<int>> graph
;
graph
.resize(vertexSize
);
for (int i
= 0; i
< vertexSize
; i
++)
{
graph
[i
].resize(vertexSize
);
}
vector
<vector
<int>> path
;
int departure
= 0;
int destination
= 99;
dijstra(graph
, path
, departure
, destination
);
return 0;
}
经典问题
正权单源最短路
问题描述
例题演示
PTA 1018 Public Bike Management (30分)[DFS][单源最短路径]
实现
cpp
参考文献
我滴脑子
