Dijkstra算法有些类似于最小生成树中prim算法，从源点出发，每次选出一个最短路径，然后依次更新n次。
下面是代码实现
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int maxv=101; const int inf=10000000; struct node{ int v,weight; }; vector<node>Adj[maxv] ; bool vis[101];//标记 int dis[101];//记录最短距离 int pre[101];//记录路径 //dijkstra算法 void dijkstra (int n) { fill(vis,vis+n,false); fill(dis,dis+n,inf); //初始化dis和vis for(int i=0;i<n;i++) pre[i]=i; //路径初始化 dis[0] =0;//这里求零点到各点最短距离 for(int i=0;i<n;i++) //循环n次 { int min=inf,u=-1; for(int j=0;j<n;j++) //找最短距离点 ，这里可以用优先队列存储dis下标更快 { if(!vis[j]&&dis[j]<min) { u=j; min=dis[j]; } } if(u==-1) return ;//没有找到 vis[u] =true;//标记已经找到的u for(int j=0;j<Adj[u].size();j++) //更新dis { int x=Adj[u][j].v; if(!vis[x]&&dis[u]+Adj[u][j].weight<dis[x]) {dis[x]=dis[u]+Adj[u][j].weight; pre[x]=u;//到达x的前一个端点是u } //遇到一些问题此处可以加第二条件，比如边权、点权、多少条最短路径等 } } } void dfs(int s,int n){//输出路径 if(pre[n]==s) { printf("%d ",s); return; } dfs(s,pre[n]); printf("%d ",n); } int main(){ return 0; }
实际上，上面的程序只储存了一条路径，如果可能有多条路径并要求都打印出来怎么办？
这时将pre变成vector<int>型自然就可以存放多条路径，然后在dfs里面递归输出即可。
那么问题又来了，如果两条路径相同时，叫你选择出花费最少、字典序最小、点权和最大等一些条件怎么办?
有两个思路：
1.前面提到dfs里面可以输出多条路径，不如在遍历这些路径的时候，记录下符号其他条件的路径，保持更新即可，这是Dijkstra+dfs算法的解决思路。
2.也可以直接在执行Dijkstra过程中解决，其有一个更新dis的操作，在更新这个操作的时候我们可以同时也更新花费、点权和等其他条件
前者具有通用性，特别是一定要输出路径时，推荐使用前者，如果只是要一个值，后者比较简洁，下面两种方法的应用：
Dijkstra+Dfs+邻接表：
https://blog.csdn.net/qq_36684096/article/details/104728599
Dijkstra+邻接矩阵+第二指标：
https://blog.csdn.net/qq_36684096/article/details/104728264
