Dijkstra

Dijkstra算法

• 背景

  在一个图中，怎样找到一个点，到其余任何一个点的权值最小的路径，这个就是最短路径问题。

• 算法思想

  • 从点入手

    我们从点的角度考虑，每次选择最短的路径，然后将新的端点家啊如考虑的集合。

  • 更新判断

    我们会遇到一个问题就是，如果新的点构成一条更短的路径，所以每加入一个点，就进行一个检查

  • INF

    INF来建立，已判断是否相连

• 代码设计

  • final数组

    final数组来判断是否已经有最短路径

    final[i] = 0;	// 0代表没有找到

  • Path数组

    Path来记录到达每一个对应的顶点的上一个前驱结点

    typedef int Patharc[MVNum];		//存储最短路径的下标的数组
    typedef int ShortPathTable[MVNum];	//存储各点的最小路径的权值和

  • 判断

    记住更新判断

    for (v = 1; v < G.vexnum; v++)
    	{
    		min = INF;
    		for (w = 0; w < G.vexnum; w++)
    		{
    			if (!final[w] && C[w] < min)
    			{
    				min = C[w];	//不用考略的原因在于final
    				k = w;
    			}
    		}
    		final[w] = 1;	//找到了就先标记一个然后开始更新检查
    		for (w = 0; w < G.vexnum; w++)
    		{
    			if (!final[w] && min + G.arcs[k][w] < C[w])
    			{
    				P[w] = k;		// 保证了找到到每一个点的最短路径
    				C[w] = min + G.arcs[k][w];
    			}
    		}
    	}

• 完整代码

  #define _CRT_SECURE_NO_WARNINGS
  #include<iostream>
  #include<cstdio>
  #include<cstdlib>
  #include<string>
  using namespace std;
  // Macro
  #define MVNum	50
  #define MAXEDGE	50
  #define INF	0x3F3F3F3F
  #define OK	1
  #define BAD	0
  #define MAXSIZE	100
  // 迪杰斯特拉算法本质是一种贪心算法
  
  // AMGraph
  using VerTexType = char;
  using ArcType = int;
  using AMGraph = struct {
  	int vexnum;
  	int arcnum;
  	VerTexType vertices[MVNum];
  	ArcType arcs[MVNum][MVNum];
  };
  
  typedef int Patharc[MVNum];		//存储最短路径的下标的数组
  typedef int ShortPathTable[MVNum];	//存储各点的最小路径的权值和
  
  void Dijkstra(const AMGraph& G, int v0,Patharc P, ShortPathTable C)
  {
  	int v, w, k, min;	//以前的一种习惯
  	int final[MVNum];	// 这个数组用来判断 一个点是否已经找到了最短路径
  	for (int i = 0; i < G.vexnum; i++)//初始化
  	{
  		final[i] = 0;	// 0代表没有找到
  		P[i] = v0;//假设每个都设为v0
  		C[i] = G.arcs[v0][i];	//	同理为到v0 的距离 第一次一定满足
  	}
  	final[v0] = 1;
  	//P[v0] = v0;  目前似乎可以不用
  	C[v0] = 0;
  	for (v = 1; v < G.vexnum; v++)
  	{
  		min = INF;
  		for (w = 0; w < G.vexnum; w++)
  		{
  			if (!final[w] && C[w] < min)
  			{
  				min = C[w];	//不用考略的原因在于final
  				k = w;
  			}
  		}
  		final[w] = 1;	//找到了就先标记一个然后开始更新检查
  		for (w = 0; w < G.vexnum; w++)
  		{
  			if (!final[w] && min + G.arcs[k][w] < C[w])
  			{
  				P[w] = k;		// 保证了找到到每一个点的最短路径
  				C[w] = min + G.arcs[k][w];
  			}
  		}
  	}
  
  }

总结

贪心思想，每次选择最优解，妙处在这个记录路径的数据结构，以及判断的选择，标记的思想。