视频教程:https://www.bilibili.com/video/BV1ts41157Sy
——图片取自视频截图
过程主要分两部：
- 1.将与当前点所连通的所有点找出来，并标记距离。
- 2.从离得最近的点开始重复第一步
- 3.直到所有的点都遍历完成
算法可视化：https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html
- 从起始点开始，寻找所有可能的路径（这里以0为起始点）
- 将与当前点所连接的所有点都搜索一遍（广度优先遍历），标记各顶点与当前位置的距离，当前点已经来过，将Known标记为True。
- 在所有连接的顶点中，找最小的边（最短距离）的顶点。从该最小距离的顶点出发重复上述步骤
- 遍历完所有的顶点后，我们将得到从起始点到所有顶点的最短距离Cost。
- 根据每个结点Path的依赖关系，我们可以达到某两个顶点之间的最短路径。例如：从0->2的最短路径是Cost为7，而2顶点可以从1顶点到达，则反推值1顶点发现1顶点可以由0顶点达到，最后得到路径为0->1>2。
python实现
from typing import Tuple
import math
import heapq
import pandas as pd
graph = {
"A": {
"B":5,"C": 1},
"B": {
"A": 5,"C":2,"D":1},
"C": {
"A":1,"B":2,"D":4,"E": 8},
"D": {
"B": 1, "C":4,"E": 3,"F": 6},
"E": {
"C": 8,"D": 3,"X":7},
"F": {
"D": 6,"Y":3},
"X": {
},
"Y": {
}
}
# graph = {
# "A": {"B":5,"C": 1},
# "B": {"A": 5,"C":2,"D":1},
# "C": {"A":1,"B":2,"D":4,"E": 8},
# "D": {"B": 1, "C":4,"E": 3,"F": 6},
# "E": {"C": 8,"D": 3,},
# "F": {"D": 6,}
# }
def init_distance(graph:dict, s:str)->dict:
distance = {
s:0}
for vertex in graph:
if vertex != s:
distance[vertex] = math.inf
return distance
def dijkstra(graph:dict, s:str)->Tuple[dict,dict]:
pqueue = [] # 数组，模拟优先级队列
heapq.heappush(pqueue, (0, s)) # 每个结点保存 (边权值 顶点)
seen = set() # 保存已遍历的顶点
parent = {
s:None} # 顶点-路径关系
distance = init_distance(graph, s) # 顶点-距离关系
while (len(pqueue) > 0): # while pqueue
pair = heapq.heappop(pqueue)
dist = pair[0]
vertex = pair[1]
seen.add(vertex)
nodes = graph[vertex].keys() # 顶点A所能达到的所有其他顶点
for w in nodes:
if w not in seen: # 该顶点还没有遇见过
if dist + graph[vertex][w] < distance[w]:
heapq.heappush(pqueue, (dist + graph[vertex][w], w))
parent[w] = vertex
distance[w] = dist + graph[vertex][w]
return parent, distance
parent, distance = dijkstra(graph, "A") # 调用算法
print( pd.DataFrame( # 以表格方式输出
[parent.values(),distance.values()], # 数据
index=["parent","distance"], # 行名
columns=parent.keys()) ) # 列名
# 求任意两点之间最短路径
''' 思路： 1. 如果两点路径不分叉，即对于路径 A->C->B->D->F->Y， 任意 C F 之间的最短路径即为他们之间的差值 详细path计算，通过parent数组逆推：patent[F]->D, parent[D]->B, parent[B]->C 2. 如果两点路径分叉，则需要查到公共的祖先结点 ↑→ F->Y 例如： A->C->B->D->E->X 求 X Y 最短路径，则需要先计算出公共的祖先结点 -》D 详细path计算：前缀：X..D + 后缀：D..Y 最短路径和计算： dist[X] - dist[comm] + dist[Y] - dist[comm] '''
print("求最短路径: 输入起点，终点:")
while True:
start, end = input("->:").split()
if start in distance.keys() and end in distance.keys():
pre = [] # 前缀
path = [] # 计算路径,end
comm, cur = start, end # 如果没有分叉，comm公共祖先结点就是start，有分叉comm更新至公共结点
while cur and cur != start:
path.append(cur)
cur = parent[cur]
if start == cur: # 找到最短路径
path.append(cur)
path.reverse()
else:# 没有找到，start与end不在一条路径上，此时需要start也回溯找公共祖先结点
while comm not in path:
pre.append(comm)
comm = parent[comm]
# comm为公共祖先结点
path = pre + path[path.index(comm)::-1]
print("\tpath: ",path)
length = distance[end] - distance[comm] + distance[start] - distance[comm]
print("\tlength: ",length)
else:
print("输入有误，无此顶点信息")
无向图：
运行效果：
c++版，这里使用数字代替英文字母顶点
class dijkstra {
private:
int n;
vector<int>& vertex; // 顶点
vector<vector<pair<int, int>>> e; // 邻接表
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q; // 优先级队，每次取最近的顶点
vector<bool> vis;
vector<int> path; // path
vector<int> distance; // distance
public:
dijkstra(vector<int>& _vertex, vector<vector<int>>& edges, int begin)
:n(_vertex.size()),
vertex(_vertex),
e(n),
vis(n),
path(n),
distance(n)
{
// 邻接表建图
for (auto& ed : edges) {
e[ed[0]].emplace_back(pair(ed[1], ed[2]));
e[ed[1]].emplace_back(pair(ed[0], ed[2])); // 无向图
}
start(begin);
}
void showDijkstraFrom(int begin, int end) {
if (begin < 0 || begin >= n || end < 0 || end >= n)
throw "begin或end范围有误，请输入范围[0~" + to_string(n) + ")";
int comm = begin, cur = end;
// 计算路径
if (begin > end) {
swap(comm, cur);
}
vector<int> resPath;
while (cur != -1 && cur != comm) {
resPath.emplace_back(cur);
cur = path[cur];
}
if (cur != -1) {
resPath.emplace_back(comm);
}
else {
// 找不到begin，则说明 begin与end是分叉路
vector<int> prePath;
auto it = std::find(resPath.rbegin(), resPath.rend(), comm);
while (resPath.rend() == it) {
// 没找到
prePath.emplace_back(comm);
comm = path[comm];
it = std::find(resPath.rbegin(), resPath.rend(), comm);
}
// 找到公共祖先顶点 begin，迭代器 res
while (it != resPath.rend()) {
prePath.emplace_back(*it);
it++;
}
resPath.swap(prePath); // 统一通过resPath存储详细路径
}
if (resPath.front() != begin) {
std::reverse(resPath.begin(), resPath.end());
}
cout << "\t路径：";
for (auto res : resPath) {
cout << res << " ";
}
int dist = distance[begin] - distance[comm] + distance[end] - distance[comm];
cout << "\n\t距离：" << dist;
cout << endl;
}
void show_table() {
cout << "vertex:\t";
for (auto v : vertex) {
cout << (char)(v + 'A') << ",";
}
cout << "\npath:\t";
for (auto p : path) {
cout << (char)(p + 'A') << ",";
}
cout << "\nparent:\t";
for (auto dist : distance) {
cout << dist << ",";
}
cout << endl;
}
private:
void start(int begin) {
q.emplace(begin, 0);
vis[begin] = true;
path[begin] = -1;
// 广度优先搜索
while (!q.empty()) {
auto [dist, cur] = q.top();
q.pop();
vis[cur] = true;
for (auto [nxt, ndist] : e[cur]) {
/* nxt 下一个顶点， ndist 到下一个顶点的距离 */
if (!vis[nxt]) {
// nxt未访问过
if (distance[nxt] == 0 || dist + ndist < distance[nxt]) {
q.emplace(dist + ndist, nxt); // 将nxt结点入队
path[nxt] = cur;
distance[nxt] = dist + ndist;
}
}
}
}
}
};
int main()
{
vector<int> vertex = {
0,1,2,3,4,5,6, 7 }; // A,B,C,D,E,F
vector<vector<int>> edges{
{
0,1,5},{
0,2,1},
{
1,2,2},{
1,3,1},
{
2,3,4},{
2,4,8},
{
3,4,3},{
3,5,6},
{
5,7,3},{
4,6,7}
};
dijkstra dij(vertex, edges, 0);
dij.show_table();
cout << "求最短路径\n->";
int begin, end;
while ((cin >> begin), begin != -1) {
// 输入-1结束
cin >> end;
try
{
dij.showDijkstraFrom(begin, end); // ...
}
catch (string& e)
{
cout << " error:" << e << endl;
}
cin.clear(); //清除cin的错误状态
cin.ignore(); //忽略掉缓冲区的内容
}
return 0;
}
这里在提供一个顶点值为string类型的版本
class dijkstra {
const string null = " "; // 起始顶点无parent
private:
int n;
unordered_set<string> vertex; // 顶点
unordered_map<string, int> mp; // 辅助表：例如 xiaoming放在邻接表第0行，xiaoqiang --- 1 ...
vector<unordered_map<string,int>> e; // 邻接表
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>> q; // 优先级队，每次取最近的顶点
vector<bool> vis;
unordered_map<string,pair<string,int>> path_dist; // path and distance
public:
dijkstra(vector<string>& _vertex, vector<vector<string>>& edges, string begin)
:n(_vertex.size()),
vertex(_vertex.begin(), _vertex.end()),
e(n),
vis(n)
{
// 初始化mp，将每个名字对应到邻接表的每一行
int i = 0;
for (const auto s : vertex) {
mp[s] = i++;
}
// 邻接表建图
for (auto& ed : edges) {
e[mp[ed[0]]].emplace(make_pair(ed[1], stoi(ed[2])));
e[mp[ed[1]]].emplace(make_pair(ed[0], stoi(ed[2]))); // 无向图
}
start(begin);
}
void showDijkstraFrom(string& begin, string& end) {
if (!vertex.count(begin) || !vertex.count(end))
throw "begin或end范围有误，请输入范围[0~" + to_string(n) + ")";
string comm = begin, cur = end;
// 计算路径
if (begin > end) {
swap(comm, cur);
}
vector<string> resPath;
while (cur != null && cur != comm) {
resPath.emplace_back(cur);
cur = path_dist[cur].first;
}
if (cur != null) {
resPath.emplace_back(comm);
}
else {
// 找不到begin，则说明 begin与end是分叉路
vector<string> prePath;
auto it = std::find(resPath.rbegin(), resPath.rend(), comm);
while (resPath.rend() == it) {
// 没找到
prePath.emplace_back(comm);
comm = path_dist[comm].first;
it = std::find(resPath.rbegin(), resPath.rend(), comm);
}
// 找到公共祖先顶点 begin，迭代器 res
while (it != resPath.rend()) {
prePath.emplace_back(*it);
it++;
}
resPath.swap(prePath); // 统一通过resPath存储详细路径
}
if (resPath.front() != begin) {
std::reverse(resPath.begin(), resPath.end());
}
cout << "\t路径：";
for (auto res : resPath) {
cout << res << " ";
}
int dist = path_dist[begin].second - path_dist[comm].second + path_dist[end].second - path_dist[comm].second;
cout << "\n\t距离：" << dist;
cout << endl;
}
void show_table() {
cout << "\nvertex: ";
for (const auto& ver : path_dist) {
cout << ver.first << ", ";
}
cout << "\npath: ";
for (const auto& path : path_dist) {
cout << path.second.first << ", ";
}
cout << "\ndistance: ";
for (const auto& path : path_dist) {
cout << path.second.second << ", ";
}
cout << endl;
}
private:
void start(string begin) {
q.emplace(make_pair(0,begin));
vis[mp[begin]] = true;
path_dist[begin] = make_pair(null, 0);
// 广度优先搜索
while (!q.empty()) {
auto [dist, cur] = q.top();
q.pop();
vis[mp[cur]] = true;
for (auto [nxt, ndist] : e[mp[cur]]) {
/* nxt 下一个顶点， ndist 到下一个顶点的距离 */
if (!vis[mp[nxt]]) {
// nxt未访问过
if(path_dist[nxt].second == 0 || dist + ndist < path_dist[nxt].second){
q.emplace(dist + ndist, nxt); // 将nxt结点入队
path_dist[nxt] = make_pair(cur, dist + ndist);
}
}
}
}
}
};
int main()
{
vector<string> vertex = {
"A","B","C","D","E","F" }; // A,B,C,D,E,F
vector<vector<string>> edges{
{
"A","B","5"},{
"A","C","1"},
{
"B","C","2"},{
"B","D","1"},
{
"C","D","4"},{
"C","E","8"},
{
"D","E","3"},{
"D","F","6"}
};
dijkstra dij(vertex, edges, "A");
dij.show_table();
cout << "求最短路径\n->";
string begin, end;
while ((cin >> begin), begin != "exit()") {
// 输入exit()结束
cin >> end;
try
{
dij.showDijkstraFrom(begin, end); // ...
}
catch (string& e)
{
cout << " error:" << e << endl;
}
}
return 0;
}
文章评论