Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。其主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止
代码实现：
#include
#include
#include
#include
using namespace std;
const int N = 510;
int n,m;
int g[N][N];//存放点到点的边权
int dist[N];//存放到起点的距离
bool st[N];//判断该点是否已经被扩展了
int dijkstra()
{
memset(dist, 0x3f, sizeof(dist));//初始化每个点到起点的距离为无穷远
dist[1] = 0;
for(int i = 0; i < n;i++)
{
int t = -1;
//寻找当前距离起点最近且没有被扩展的点用来更新其它所有点到起点的距离
for(int j = 1; j dist[j]))//如果当前点没有被遍历过，并且没有选中一个点或者当前点到起点距离小于选中的点到起点的距离
t = j;
st[t] = true;
for(int j = 1; j
Original: https://www.cnblogs.com/amour233/p/16473359.html
Author: LYL233
Title: Dijkstra算法求最短路
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588281/
转载文章受原作者版权保护。转载请注明原作者出处！