引入
迪科斯彻提出了著名的单源最短路径求解算法——Dijkstra算法。
Dijkstra算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。
Dijkstra算法的基本思想是首先假定源点为u，顶点集合V被划分为两部分:集合S和V-S。初始时S中仅含有源点u，其中S中的顶点到源点的最短路径已经确定。集合V-S中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过S中的点到达V-S中的点的路径为特殊路径，并用数组dist[]记录当前每个顶点所对应的最短特殊路径长度.
Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径，将其连接的V-S中的顶点加入到集合S中，同时更新数组dist[]。一旦S包含了所有顶点，dist[]就是从源到所有其他顶点之间的最短路径长度。
算法步骤:
数据结构。设置地图的带权郐接矩阵为G.Edge[][],即如果从源点u到顶点i有边，
就令G.Edge[u][i]等于<u，i>的权值，否则G.Edge[u][i]=∞(无穷大);采用一维数组dist[i]来记录从源点到i顶点的最短路径长度;采用一维数组p[i]来记录最短路径上i顶点的前驱。
初始化。令集合S={u}，对于集合V-S中的所有顶点x,初始化dist[1]=G.Edge[u][i],
如果源点u到顶点i有边相连，初始化p[i]=u，否则p[i]=-1。
找最小。 在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t，即
dist[t]=min (dist [ j ] | j属于V-S集合)，则顶点t就是集合V-S中距离源点u最近的
顶点。
加入S战队。将顶点t加入集合S中，同时更新V-S。
判结束。如果集合V-S为空，算法结束，否则转6。
借东风。在 3 中已经找到了源点到t的最短路径，那么对集合V-S中所有与顶点
t相邻的顶点j，都可以借助t走捷径。如果dis[j>dist[t]+G.Edge[]Ii]， 则
dist[i]=dist[t]+G.Edge[ t ][ i ],记录顶点j的前驱为t，即p[i]=t,转3。
参考代码
#include<iostream> #include<stack> #include<string.h> #include<string> using namespace std; const int MaxVnum=100; // 城市的个数可修改 const int INF=1e7; // 无穷大10000000 int dist[MaxVnum],p[MaxVnum];//最短距离和前驱数组 bool flag[MaxVnum]; //如果s[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S typedef string VexType; //顶点的数据类型，根据需要定义 typedef int EdgeType; //边上权值的数据类型，若不带权值的图，则为0或1 typedef struct { VexType Vex[MaxVnum]; EdgeType Edge[MaxVnum][MaxVnum]; int vexnum,edgenum; //顶点数，边数 } AMGragh; int locatevex(AMGragh G,VexType x) { for(int i=0; i<G.vexnum; i++) //查找顶点信息的下标 if(x==G.Vex[i]) return i; return -1;//没找到 } void CreateAMGraph(AMGragh &G) { int i,j,w; VexType u,v; cout << "请输入顶点数："<<endl; cin>>G.vexnum; cout << "请输入边数:"<<endl; cin>>G.edgenum; cout << "请输入顶点信息:"<<endl; for(int i=0; i<G.vexnum; i++) //输入顶点信息，存入顶点信息数组 cin>>G.Vex[i]; for(int i=0; i<G.vexnum; i++) //初始化邻接矩阵为无穷大 for(int j=0; j<G.vexnum; j++) G.Edge[i][j]=INF; cout << "请输入每条边依附的两个顶点及权值："<<endl; while(G.edgenum--) { cin>>u>>v>>w; i=locatevex(G,u);//查找顶点u的存储下标 j=locatevex(G,v);//查找顶点v的存储下标 if(i!=-1&&j!=-1) G.Edge[i][j]=w; //有向图邻接矩阵 else { cout << "输入顶点信息错！请重新输入！"<<endl; G.edgenum++;//本次输入不算 } } } void Dijkstra(AMGragh G,int u) { for(int i = 0; i < G.vexnum; i++) {//初始化源点u到其他各个顶点的最短路径长度 dist[i] = G.Edge[u][i];//初始化dist flag[i] = false; if(dist[i]==INF) { p[i]=-1;//源点u到改顶点的路径长度为无穷大,说明顶点i与源点不相邻 } else { p[i] = u;//说明顶点i与源点u相邻,设置顶点i的前驱p[i] = u; } } dist[u] = 0; flag[u] = true;//初始时,集合S中只有一个元素:源点u for(int i = 0; i < G.vexnum; i++) { int temp = INF,t = u; for(int j = 0; j < G.vexnum; j++) { //集合V-S中寻找距离源点u最近的顶点t if(!flag[j]&&dist[j]<temp) { t = j; temp = dist[j]; } } if(t==u) { return;//找不到t,说明V-S中已经没有节点了,跳出循环 } flag[t] = true;//找到则将t加入集合 for(int j = 0; j < G.vexnum; j++) { //跟新与t相邻接的顶点到源点u的距离 if(!flag[j]&&G.Edge[t][j]<INF) {//依旧是更新V-S中的点 但必须是t->j的这种邻接点. 否则t的加入对j最短路径毫无影响 if(dist[j]>(dist[t]+G.Edge[t][j])) {//判断在t的加入下,路径是否变短了 dist[j] = dist[t]+G.Edge[t][j]; p[j] = t;//跟新节点前驱 } } } } } void findpath(AMGragh G,VexType u) { int x; stack<int> S; cout<<"源点为: "<<u<<endl; for(int i = 0; i < G.vexnum; i++) { x = p[i]; if(x==-1&&u!=G.Vex[i]) {//dis的前驱为-1但不是源点则说明无路可达. cout<<"源点到"<<G.Vex[i]<< "无路可达!!!"<<endl; continue; } while(x!=-1) { S.push(x);//存放的是下标 x = p[x]; } cout<<"源点到"<<G.Vex[i]<<"顶点的最短路径为: "; while(!S.empty()) { cout<<G.Vex[S.top()]<<"---"; S.pop(); } cout<<G.Vex[i]<<"\t最短距离为:"<<dist[i]<<endl; } } int main() { AMGragh G; int st; VexType u; CreateAMGraph(G); cout<<"请输入源点的信息:"<<endl; cin>>u; st= locatevex(G,u);//查找源点u的存储下标 Dijkstra(G,st); findpath(G,u); return 0; } /* 0 1 1 0 3 4 1 2 9 1 3 2 2 1 5 2 0 3 2 3 8 3 2 6 */
运行结果:
算法分析:
算法优化:
下面是优先队列和链式前向星的优化:
#include<bits/stdc++.h> using namespace std; const int maxn = 100;//节点数 const int INF = 0x3f3f3f3f; int n,m,start,cnt,num,head[maxn],dist[maxn],p[maxn];//head:节点数组 dist:存放最短距离, p:存放前驱 struct node{ int to,next,w; }edge[maxn*maxn];//边集数组 void add(int u,int v,int w){ edge[++num].next = head[u]; edge[num].to = v; edge[num].w = w; head[u] = num; } struct cmp{//仿函数,用于优先队列数据的比较 bool operator()(int &a,int &b){ return dist[a]>dist[b]; } }; void Dijkstra(int x){ //用优先队列寻找V-M中的最小值,来代替傻瓜式 搜索,节约时间 priority_queue<int,vector<int>,cmp > Q; memset(dist,INF,sizeof(dist)); memset(p,-1,sizeof(p)); dist[x] = 0; Q.push(x); while(!Q.empty()){ int u = Q.top(); Q.pop(); for(int i = head[u]; i; i = edge[i].next){ int v = edge[i].to; if(dist[v]==INF){//如果是无穷大,说明未在V-M中,则加入队列 Q.push(v); } if(dist[v]>dist[u]+edge[i].w) { dist[v] = dist[u]+edge[i].w; p[v] = u; //cout<<u<<endl; } } } } void findPath(int u){ int x; stack<int> s; for(int i = 1; i <= n; i++){ x = p[i]; if(x==-1&&i!=u){ cout<<"源点到"<<i<<"无路可达!!!"<<endl; continue; } while(x!=-1){ s.push(x); x = p[x]; } cout<<"源点到"<<i<<"顶点的最短路径为: "; while(!s.empty()) { cout<<"--->"<<s.top(); s.pop(); } cout<<"\t最短距离为"<<dist[i]<<endl; } } int main(){ int u,v,w; cin>>n>>m>>start; for(int i = 0; i < m; i++){ cin>>u>>v>>w; add(u,v,w); } Dijkstra(start); //cout<<"hahha"<<endl; findPath(start); return 0; }
代码分析:易知每次寻找最小值都是在V-S中寻找的,第一次直接是源点不用寻找,然后更新dist,并将其加入到队列中,第二次是从队列中弹出一个最小的(不在队列中的V-S点不用考虑,因为他们都是无穷大,而我们要找的是最小值,),然后继续更新dist,每次在更新时,如果某个结点的dist为无穷大,则说明之前没有加入过,将其加入即可.然后如果在最小值的加入下该点的dist更小了,则更新dist和p.
