一. 概述
Dijkstra算法是求一个顶点到其余各顶点的最短路径算法-
迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略
每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止
二. 算法流程
- 建立图的存储结构（邻接矩阵/邻接表）
- 初始化图
- 初始化源点到各点路径长度
- 初始化当前访问顶点集合并将源点加入
- 贪心寻找下一个未入集合的最近节点
- 将该节点加入已经访问顶点集合
- 以该节点为媒介更新其他顶点距离（未访问）
- 重复567操作n-1次
- 返回结果
三. 实例
vector<vector<int>> graph;//邻接矩阵
Graph(int n, vector<vector<int>>& edges) {//初始化图
graph.resize(n);
for(auto &point:graph)
point.resize(n,INT_MAX);//初始赋无穷远距离
for(int i=0;i<edges.size();i++){
int from = edges[i][0];
int to = edges[i][1];
int cost = edges[i][2];
graph[from][to] = cost;
}
}
void addEdge(vector<int> edge) {//加入边
int from = edge[0];
int to = edge[1];
int cost = edge[2];
graph[from][to] = cost;
}
获取起点到终点的最短路径长度
int shortestPath(int node1, int node2) {
if(node1==node2) return 0;
int n =graph.size();
vector<int> dis(n);//记录到各点的距离
vector<bool> mark(n);//标记访问情况
mark[node1] = true;//加入源点
for(int i=0;i<n;i++)
dis[i] = graph[node1][i];//初始化源点到各点距离
for(int count=1;count<n;count++){//更新n-1次
int minpath = INT_MAX;//记录最小距离
int nextpoint = -1;//下一个邻近节点
for(int i=0;i<n;i++)//贪心找下一个最近节点
{
if(mark[i]==0&&dis[i]<minpath){
minpath = dis[i];
nextpoint = i;
}
}
if(nextpoint==node2) return dis[node2];
//如果没有下一个邻近节点
if(nextpoint==-1) return -1;
mark[nextpoint] = true;//将节点加入访问集合
for(int i=0;i<n;i++){//根据新加入的节点更新所有节点离源点的距离
if(graph[nextpoint][i]<INT_MAX&&mark[i]==false){//该点到新加入节点有边
if(dis[i]>dis[nextpoint]+graph[nextpoint][i])
dis[i]=dis[nextpoint]+graph[nextpoint][i];//更新该点到源点距离
}
}
}
return dis[node2]==INT_MAX?-1:dis[node2];
}