[C++]单源最短路径：迪杰斯特拉(Dijkstra)算法(贪心算法)

概述1 Dijkstra算法 1.1 算法基本信息 解决问题/提出背景 单源最短路径（在带权有向图中，求从某顶点到其余各顶点的最短路径） 算法思想 贪心算法 按路径长度递增的次序，依次产生最短路径的算法 【适用范围】Dijkstra算法仅适用于【权重为正】的图模型中 时间复杂度 O(n^3) 补充说明 亦可应用于【多源最短路径】(推荐：Floyd算法(动态规划,O(n^3))) Dijkstra 时间 1 Dijkstra算法 1.1 算法基本信息 解决问题/提出背景 单源最短路径（在带权有向图中，求从某顶点到其余各顶点的最短路径） 算法思想 贪心算法 按路径长度递增的次序，依次产生最短路径的算法 【适用范围】Dijkstra算法仅适用于【权重为正】的图模型中 时间复杂度 O(n^3) 补充说明 亦可应用于【多源最短路径】(推荐：Floyd算法(动态规划,O(n^3)))

Dijkstra 时间复杂度：O(n^3)

1.2 算法描述 1.2.1 求解过程(具体思路)

1.2.2 示例

1.2 编程复现 1> 定义图模型(邻接矩阵表示法)的【基本存储结构体】

# define MaxInt 32767 // 表示极大值 即 ∞ (无穷大)# define MVNum 100 // 最大顶点数 typedef int VertexType; // 假设顶点的数据类型为整型typedef int ArcType; // 假设Vi与Vj之边的权值类型为整型 typedef struct {    VertexType vexs[MVNum]; // 顶点表 (存储顶点信息)    ArcType arcs[MVNum][MVNum]; // 邻接矩阵    int vexnum,arcnum; // 图的当前顶点数与边数 }AMGraph; // Adjacent Matrix Graph 邻接矩阵图@H_502_73@ 2> 定义 Dijkstra 算法的【辅助数据结构体】   
 
bool S[MVNum]; // S[i] 记录从源点V0到终点Vi是否已被确定为最短路径长度  【划分确定与未确定: 跟贪心算法的适用范围(不可取消性)有直接联系】               // true：表已确定；false：表尚未确定ArcType D[MVNum]; // D[i] 记录从源点V0到终点Vi的【当前】最短路径【长度】 int Path[MVNum];  // Path[i] 记录从源点V0到终点Vi的【当前】最短路径上【Vi的[直接前驱]的顶点序号】@H_502_73@ 3> 初始化(邻接矩阵)带权有向图的图模型 
voID InitAMGraph(AMGraph &G){    cout<<"Please input Vertexs Number:";    cin>>G.vexnum;    cout<<"\nPlease Directed Edges Number:";    cin>>G.arcnum;        for(int i=0;i<MVNum;i++){        for(int j=0;j<MVNum;j++){            if(i!=j){ // 【易错】 初始化<Vi,Vj>时: <Vi,Vj> 路径长度无穷大 (i!=j)                 G.arcs[i][j] = MaxInt;            } else { //  【易错】 初始化<Vi,Vi>【自回环】路径长度为0 (i==i)                 G.arcs[i][j] = 0;            }        }    }    for(int i=0;i<G.vexnum;i++){        G.vexs[i] = i;    }    cout<<"\nPlease input All Directed Edges and their Weight Now:";    cout<<"\nDirected Edges(i,j,weight): "<<endl;    int i,j;    int weight;    for(int k=0;k<G.arcnum;k++){//      cout<<"("<<(k+1)<<") ";        cin>>i;cin>>j;cin>>weight;        G.arcs[i][j] = weight;    }    cout<<endl;}@H_502_73@ 4> Dijkstra算法：求解单源最短路径 
voID ShortestPath_Dijkstra(AMGraph G,int V0){    //step1 n个顶点依次初始化    int n =G.vexnum;      for(int v=0;v<n;v++){        S[v] = false;        D[v] = G.arcs[V0][v];        if(D[v]<MaxInt){            Path[v] = V0;        } else {            Path[v] = -1;        }    }    //step2 将源点V0划入已确定集合S中     S[V0] = true;    D[V0] = 0; // 源点V0到源点V0的最短路径长度必然为0    //step3 贪心算法策略：    //          3.1 循环遍历所有结点：    //              3.2 先确定当前最短路径的终点v；    //              3.3 然后，将v划入已确定集合S中；    //              3.4 最后，以利用结点v更新所有尚未确定的结点的最短路径    int v;    int min;    D[G.vexnum] = MaxInt;    for(int i=1;i<n;i++){//3.1循环遍历所有结点 （即 求从源点V0到图中每一顶点(共计n-1个顶点)的最短路径）         //3.2 确定当前最短路径的终点v；        min = MaxInt;        for(int w=0;w<n;w++){            if(S[w]==false && D[w]<min){//比本轮循环中，已知的最短路径还短 【易错/易漏】 S[w]==false ： 必须满足当前结点 Vw 属于尚未确定的结点                 v = w;                min = D[w];            }        }        //3.3 然后，将v划入已确定集合S中；        S[v] = true;        //3.4 最后，以利用结点v更新所有尚未确定的结点的最短路径        for(int w=0;w<n;w++){            //↓更新Vw结点的最短路径长度为 D[v] + G.arcs[v][w]             //cout<<"S["<<w<<"]:"<<S[w]<<"D["<<v<<"]"<<D[v]<<"G.arcs["<<v<<"]["<<w<<"]"<<"D["<<w<<"]"<<D[w]<<endl;             if(S[w]==false && (D[v] + G.arcs[v][w] < D[w])){//【易错/易漏】 S[w]==false ： 必须满足当前结点 Vw 属于尚未确定的结点                 D[w] = D[v] + G.arcs[v][w];                Path[w] = v; // 更新 结点Vw的前驱为 v             }        }        v = G.vexnum;    } }@H_502_73@ 5> 输出结果 D[i]、Path[j] 
voID OutputD(AMGraph G,int V0){    cout<<"Shortest distance Weight of the Pair of Directed Vertices("<<V0<<",j):"<<endl;     for(int j=0;j<G.vexnum;j++){        cout<<D[j]<<"\t";     }    cout<<endl;}voID OutputPath(AMGraph G,int V0){    cout<<"Shortest distance Path("<<V0<<",j) of the Pair of Directed Vertices:"<<endl;     for(int j=0;j<G.vexnum;j++){        cout<<Path[j]<<"\t";     }    cout<<endl;}@H_502_73@ 6> 执行：Main函数 
int main(){    int V0; //源点V0的下标     AMGraph G;    InitAMGraph(G);        cout<<"Please input the Index of Source Node 'V0':";    cin>>V0;    ShortestPath_Dijkstra(G,V0);    OutputD(G,V0);    OutputPath(G,V0);    return 0;}@H_502_73@ 7> Test: Output of Main   
 
Please input Vertexs Number:6Please Directed Edges Number:8Please input All Directed Edges and their Weight Now:Directed Edges(i,weight):1 2 50 2 103 5 104 3 200 4 302 3 504 5 600 5 100Please input the Index of Source Node 'V0':0Shortest distance Weight of the Pair of Directed Vertices(0,j):0       32767   10      50      30      60Shortest distance Path(0,j) of the Pair of Directed Vertices:0       -1      0       4       0       3@H_502_73@ 2 参考文献 《数据结构(C语言版/ 严蔚敏 李冬梅 吴伟民 编)》                     	          总结       
以上是内存溢出为你收集整理的[C++]单源最短路径：迪杰斯特拉(Dijkstra)算法(贪心算法)全部内容，希望文章能够帮你解决[C++]单源最短路径：迪杰斯特拉(Dijkstra)算法(贪心算法)所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/1210134.html