标签：source   c语言版   权重   顶点   str   image   cout   结构体   png   

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 邻接矩阵图 

• 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的[直接前驱]的顶点序号】 

• 3> 初始化(邻接矩阵)带权有向图的图模型

void InitAMGraph(AMGraph &G){
    cout>G.vexnum;
    cout>G.arcnum;
    
    for(int i=0;i时:  路径长度无穷大 (i!=j) 
                G.arcs[i][j] = MaxInt;
            } else { //  【易错】 初始化时: 【自回环】路径长度为0 (i==i) 
                G.arcs[i][j] = 0;
            }
        }
    }
    for(int i=0;i>i;cin>>j;cin>>weight;
        G.arcs[i][j] = weight;
    }
    cout

• 4> Dijkstra算法：求解单源最短路径

void ShortestPath_Dijkstra(AMGraph G, int V0){
    //step1 n个顶点依次初始化
    int n =G.vexnum;  
    for(int v=0;v

• 5> 输出结果 D[i]、Path[j]

void OutputD(AMGraph G, int V0){
    cout

• 6> 执行：Main函数

int main(){
    int V0; //源点V0的下标 
    AMGraph G;
    InitAMGraph(G);
    
    cout>V0;
    ShortestPath_Dijkstra(G, V0);
    OutputD(G, V0);
    OutputPath(G, V0);
    return 0;
}

• 7> Test: Output of Main

Please Input Vertexs Number:6

Please Directed Edges Number:8

Please Input All Directed Edges and their Weight now:
Directed Edges(i,j,weight):
1 2 5
0 2 10
3 5 10
4 3 20
0 4 30
2 3 50
4 5 60
0 5 100

Please Input the Index of Source Node 'V0':0

Shortest Distance Weight of the Pair of Directed Vertices(0, j):
0       32767   10      50      30      60

Shortest Distance Path(0,j) of the Pair of Directed Vertices:
0       -1      0       4       0       3

2 参考文献

• 《数据结构(C语言版/ 严蔚敏 李冬梅 吴伟民 编)》

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

标签：source   c语言版   权重   顶点   str   image   cout   结构体   png   

原文地址：https://www.cnblogs.com/johnnyzen/p/11613609.html