C++最短路径Dijkstra算法的分析与具体实现详解

　　#include

　　using namespace std;

　　// 模拟实现Dijkstra算法，不适用于存在负值的带权图

　　#define MAXVERTEX 6

　　typedef struct {

　　char Vertex[MAXVERTEX]; //顶点集

　　int Edge[MAXVERTEX][MAXVERTEX]; // 存放权值

　　int vernum, arcnum; // 顶点数和边数

　　}MGraph;

　　// 初始化图

　　void InitGraph(MGraph& G) {

　　G.Vertex[0] = 'A';

　　G.Vertex[1] = 'B';

　　G.Vertex[2] = 'C';

　　G.Vertex[3] = 'D';

　　G.Vertex[4] = 'E';

　　G.vernum = 5;

　　G.arcnum = 10;

　　// 图中边权值均设为无穷大

　　for (int i = 0; i < G.vernum; i++) {

　　for (int j = 0; j < G.vernum; j++) {

　　G.Edge[i][j] = INT_MAX;

　　}

　　}

　　// 根据具体图形设置具体权值

　　G.Edge[0][1] = 10; // 诸如此类

　　G.Edge[0][4] = 5;

　　G.Edge[1][2] = 1;

　　G.Edge[1][4] = 2;

　　G.Edge[4][1] = 3;

　　G.Edge[2][3] = 4;

　　G.Edge[3][2] = 6;

　　G.Edge[4][3] = 2;

　　G.Edge[3][0] = 7;

　　G.Edge[4][2] = 9;

　　}

　　bool final[MAXVERTEX];

　　int dist[MAXVERTEX];

　　int path[MAXVERTEX];

　　void Dijkstra(MGraph G,int v) {

　　for (int i = 0; i < G.vernum; i++) {

　　final[i] = false;

　　dist[i] = G.Edge[v][i];

　　path[i] = (G.Edge[v][i] == INT_MAX ? -1 : v);

　　}

　　final[v] = true;

　　dist[v] = 0;

　　// 第一轮

　　int index =v; // 权值最小的边顶点下标

　　int para = INT_MAX;

　　for (int j = 0; j < G.vernum; j++) {

　　if (final[j] == false && G.Edge[v][j] < para) {

　　para = G.Edge[v][j];

　　index = j;

　　}

　　}

　　// 第二轮及以后

　　for (int i = 0; i < G.vernum; i++) {

　　for (int c = 0; c < G.vernum; c++) {

　　if (final[c] ==false && G.Edge[index][c] < INT_MAX) {

　　if (G.Edge[index][c] + dist[index] < dist[c]) {

　　dist[c] = G.Edge[index][c] + dist[index];

　　path[c] = index;

　　}

　　}

　　}

　　// 找到final 为false的顶点中权值最小的顶点下标

　　int temp = INT_MAX;

　　int in = v;

　　for (int i = 0; i < G.vernum; i++) {

　　if (final[i] == false && dist[i] < temp) {

　　temp = dist[i];

　　in = i;

　　}

　　}

　　index = in; // 更新下标

　　final[index] = true;

　　}

　　}

　　void print_path(MGraph G ,int v) {

　　cout << "对应的最短路径为：";

　　cout << G.Vertex[v] << "->";

　　for (int i = 0; i < G.vernum; i++) {

　　if (path[v] != 1) {

　　cout << G.Vertex[path[v]] << "->";

　　v = path[v];

　　}

　　}

　　cout << G.Vertex[1] << endl;

　　}

　　int main() {

　　MGraph G;

　　InitGraph(G);

　　Dijkstra(G, 1);

　　cout << "顶点B到顶点D的最小花费为："<< dist[3] << endl;

　　print_path(G, 3);

　　}