迪杰斯特拉（dijkstra）算法是典型的用来解决最短路径的算法，也是很多教程中的范例，由荷兰计算机科学家狄克斯特拉于1959年提出，用来求得从起始点到其他所有点最短路径。该算法采用了贪心的思想，每次都查找与该点距离最的点，也因为这样，它不能用来解决存在负权边的图。解决的问题大多是这样的：有一个无向图G(V,E)，边E[i]的权值为W[i]，找出V[0]到V[i]的最短路径。
算法的步骤如下：
（1）初始化时，S只含有源节点；
（2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）；
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源节点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值是顶点k的距离加上k到u的距离；
（4）重复步骤（2）和（3），直到所有顶点都包含在S中。
下面举个例子来说明这个过程，假设以A为源点。
dijkstra算法实现的完整代码如下（已测试通过）：
#include<iostream> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<cstdlib> #include<map> #include<set> #include<cstdio> #include<queue> #include<list> #include<vector> #include<stack> #include<deque> using namespace std; const int maxn=107;//点的个数 const int INF=0xfffffff;//不可达的距离 //边的结构体 struct Edge { int from; int to; int dist; Edge(int u,int v,int d):from(u),to(v),dist(d) {} }; //迪杰斯特拉的结构体 struct Dijkstra { int n,m; vector<Edge> edges; //存边 vector<int> G[maxn]; //存邻接表 bool done[maxn]; //是否已经永久标号 int d[maxn]; //s到各个点的距离 int p[maxn]; //最短路上的一条弧 /*优先队列默认最大堆，即从大到小排列， 而迪杰斯特拉算法是寻找的最小路径， 所以要选择重载的<运算符,实现最小堆*/ struct HeapNode { int d,u; bool operator < (const HeapNode& rhs) const { return d>rhs.d; } }; //初始化，将邻接表和边的vector清空 void init(int n) { this->n=n; for(int i=0; i<n; i++) G[i].clear(); edges.clear(); } //加边 void AddEdge(int from,int to,int dist) { /* 无向图需要把这6行全加上 有向图只需要加前三行 */ edges.push_back(Edge(from,to,dist)); m=edges.size(); G[from].push_back(m-1); //push的是下标，因为根据下标找到的信息更全一些 edges.push_back(Edge(to,from,dist)); m=edges.size(); G[to].push_back(m-1); } //核心算法，迪杰斯特拉算法，S是源点 void dijkstra(int s) { priority_queue<HeapNode>Q; //最小堆 for(int i=0; i<n; i++) d[i]=INF; d[s]=0; memset(done,0,sizeof(done)); Q.push((HeapNode){0,s}); //构造函数,传值给d,u，意思是某节点的距离和某节点 while(!Q.empty()) { HeapNode x=Q.top(); Q.pop(); int u=x.u; if(done[u]) continue; done[u]=true; for(int i=0; i<G[u].size(); i++) { Edge& e=edges[G[u][i]]; if(d[e.to]>d[u]+e.dist) { d[e.to]=d[u]+e.dist; p[e.to]=G[u][i]; Q.push((HeapNode){d[e.to],e.to}); } } } } }; int main() { freopen("out.txt","r",stdin); //打开文件读取文件 Dijkstra dij; int nodenum,edgenum,source; //节点数目、边的数目、源点 int from,to,weight; //一条边的起点、终点和权值 cin>>nodenum>>edgenum>>source; //初始化边图vector dij.init(nodenum); //加边 for(int i=1; i<=edgenum; i++) { cin>>from>>to>>weight; dij.AddEdge(from,to,weight); } //搜索 dij.dijkstra(source); //打印每个节点和源点的最短路 for(int i=0; i<nodenum; i++) { cout<<"源点到第"<<i<<"个点的最短路是："<<dij.d[i]<<endl; } return 0; } 输入：第一行三个数字分别是点的个数、边的条数和源点，后边9行是9条边的起点、终点和权值 6 9 0 0 1 6 0 2 3 1 3 5 1 2 2 2 3 3 2 5 4 3 5 2 3 4 3 4 5 5输出：
源点到第0个点的最短路是：0 源点到第1个点的最短路是：5 源点到第2个点的最短路是：3 源点到第3个点的最短路是：6 源点到第4个点的最短路是：9 源点到第5个点的最短路是：7
