Dijkstra规划算法原理及C++实现

1. 算法原理

参考此篇足矣：
Dijkstra算法图文详解

2. C++ 实现

问题描述：
有四个节点（ 0，1， 2， 3），已知 0和1之间的距离为3米， 1和2之间的距离为4米，2和3之间的距离为2米， 0和3之间的距离为5米。
求：1 --> 3的最短距离是多少？

思路：采用邻接矩阵法，通过二维vector保存相邻节点的距离，其中：自节点距离为0，不相连节点的距离初始化为一个很大的值INF

vector<vector<int>> global_map = {            // 纵坐标为起点，横坐标向为终点
					   /*0*/ /*1*/ /*2*/ /*3*/
				  /*0*/ {0,   3,   INF,    5},
				  /*1*/ {3,   0,   4,     INF},
				  /*2*/ {INF, 4,   0,     2},
				  /*3*/ {5,   INF, 2,     0}}   

#include <iostream>
#include <vector>
#include <algorithm>
#include "stdio.h"

using namespace std;

#define INF 99

			// 	  /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
//int global_map[][6]	=	// {
  //     /*A*/ {   0,  12, INF, INF, INF,  16,  14},
  //     /*B*/ {  12,   0,  10, INF, INF,   7, INF},
  //     /*C*/ { INF,  10,   0,   3,   5,   6, INF},
  //     /*D*/ { INF, INF,   3,   0,   4, INF, INF},
  //     /*E*/ { INF, INF,   5,   4,   0,   2,   8},
  //     /*F*/ {  16,   7,   6, INF,   2,   0,   9},
  //     /*G*/ {  14, INF, INF, INF,   8,   9,   0}};

	/*int N = sizeof(global_map) / sizeof(global_map[0]);
	int M = sizeof(global_map[0]) / sizeof(global_map[0][0]);

	vector<vector<int>> vec_map(N, vector<int>(M));
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			vec_map[i][j] = global_map[i][j];
		}
	}

	for(auto i : vec_map)
	{
		for(auto j : i)
		{
			cout<< j << " ";
		}
		cout << endl;

	}*/

void Dij(int& start, int& end, vector<vector<int>>& map, int* pre)
{
    int N = map.size();
    cout << "N = " <<N<<endl;

	int dist[N];       // dist[i]最终会保存起点到i节点的最短距离
	std::fill(dist, dist + N, INF);   // 先将每个值初始化为很大的数

	bool visit[N];
	std::fill(visit, visit + N, false);   // visit起到剪枝的作用

	for(int i = 0; i < N; i++)
	{
		pre[i] = i;            // 初始化
	}

	dist[start] = 0;       // 起点距离为0

	for(int i = 0; i < N; i++)
	{
		int u = -1;
		int min = INF;
		for(int j = 0; j < N; j++)
		{

			if(!visit[j] && dist[j] < min)     // 已经为父节点的节点就不会再参与计算，找出剩余节点的最短距离
			{

				u = j;                 // u 为父节点
				min = dist[j];         
			}
		}

		if(u == -1 || u == end)      // 是否找到终点
		{
			cout << "mh find u == end "<<endl;

			break;
		}

		visit[u] = true;       // 剪枝

		for(int v = 0; v < N; v++)
		{
			if(!visit[v] && map[u][v] != INF)
			{
				if(dist[u] + map[u][v] < dist[v])      // 是否松弛
				{
					dist[v] = dist[u] + map[u][v];     //重新更新节点距离 
					pre[v] = u;                 // 重新更新，表示节点 v 的父节点为 u

				    cout << "pre["<< v <<"] =" << u << "   " << "u_dist["<< u<<"] = " << dist[u]<< "   " ；
					cout <<"v_dist["<< v <<"] = "<< dist[v]<<endl;
				}
			}
		}
		//cout<<"test.....3"<<endl;
	}

	int t = end;
	cout<<"path = ";

	vector<int> path;   // 保存起点到终点的路径点

	while(pre[t] != t)   // 从终点往起点遍历
	{
		path.push_back(t);
		t = pre[t];
	}
	 //	下面为打印的结果，不懂的地方可以通过此数据分析		   
	 //pre[0] =1   u_dist[1] = 0   v_dist[0] = 3
	 //pre[2] =1   u_dist[1] = 0   v_dist[2] = 4
	 //pre[3] =0   u_dist[0] = 3   v_dist[3] = 8
     //pre[3] =2   u_dist[2] = 4   v_dist[3] = 6    //注意通过松弛后，pre[3]的父节点：由 0 变为 2
                                                   //dist[3]最短距离：由 8 变为 6

	path.push_back(start);

	reverse(path.begin(), path.end());
	for(auto p : path)
	{
		cout<< p <<" ";       //  path = 1 2 3 
	}
	cout<<endl;

	cout<< "Total min length = " << dist[end] << endl;   // Total min length = 6

}

int main()
{
	vector<vector<int>> global_map = { 
				  {0,   3,   INF,    5,    INF,   INF},
				  {3,   0,   4,     INF,    INF,   INF},
				  {INF, 4,   0,     2,     INF,   INF},
				  {5,   INF, 2,     0,      INF,     INF},
				  {INF, INF, INF,  INF,     INF,     INF},
				  {INF, INF, INF,  INF,   INF,     INF  }
				};

	int a[6];

	int start = 1;
	int end = 3;

	Dij(start, end, global_map, a);

	return 0;
}