Dijkstra算法

Dijkstra算法适用于边权为正的情况，用于计算正权图的单源最短路，即从单个源点出发，到所有节点的最短路。同时适用于有向图和无向图。
模板：
//处理图....begin为起点
int n,begin;
int chart[][],path[];//chart为图 path[i]为起点到i的距离
bool visit[]; //是否被访问

//初始化 起点为path为0
memset(visit,0,sizeof(visit));
for(int i = 0;i < n;i++) path[i] = (i == begin ? 0 :INF); for(int i = 0;i < n;i++){ //寻找最小节点 int u,dis = INF; for(int j = 0;j < n;j++) if(!visit[j] && path[j] < dis) dis = path[u=j]; //标记节点 visit[u] = true; //更新dist[u] if(没有被访问

Dijkstra算法最先出现在Python成神之路。