【图论】（单源最短路径）Dijkstra算法SPFA算法

Bellman--Ford算法友情链接&＃xff1a;https://blog.csdn.net/lesileqin/article/details/89194677

注&＃xff1a;以上链接包含测试数据。

Dijkstra算法邻接矩阵表示实现&＃xff1a;

#include
#define MAX_V 60
#define INF 999999
using namespace std;int cost[MAX_V][MAX_V]; //cost[u][v]表示点u到v上的权值
int d[MAX_V]; //最短距离
bool used[MAX_V]; //已经使用过的图
int V,E; //求从起点s出发到各个顶点的最短距离
void dijkstra(int s)
{fill(d,d&＃43;V,INF);fill(used,used&＃43;V,false);d[s]&＃61;0;while(true){int v&＃61;-1;//从尚未使用过的顶点中选择一个距离最小的顶点for(int u&＃61;0;u}int main()
{//初始化邻接矩阵 for(int i&＃61;0;i> V >> E;for(int i&＃61;0;i> a >> b >> c;cost[a][b]&＃61;c;}dijkstra(0);for(int i&＃61;0;i}

Dijkstra算法邻接表优先队列表示实现&＃xff1a;

#include
#include
#define MAX_V 60
#define INF 99999using namespace std;struct edge{int to,cost;
};typedef pair P; //first是最短距离、second是顶点的编号
int V,E;
vector G[MAX_V];
int d[MAX_V];
int temp;void dijkstra(int s)
{//通过指定greater

参数&＃xff0c;堆按照first从小到大顺序取出值 priority_queue,greater

> que;fill(d,d&＃43;V,INF);d[s]&＃61;0;que.push(P(0,s)); while(!que.empty()){P p&＃61;que.top();que.pop();int v&＃61;p.second;if(d[v]d[v]&＃43;e.cost){d[e.to]&＃61;d[v]&＃43;e.cost;que.push(P(d[e.to],e.to));}}}
}int main()
{cin >> V >> E;for(int i&＃61;0;i> temp >> e.to >> e.cost;G[temp].push_back(e); }dijkstra(0);for(int i&＃61;0;i}

SPFA算法模板&＃xff1a;

#include
#include
#include
#include
#include
#include
#include