图的最短路径——迪杰斯特拉算法

迪杰斯特拉算法是关于图的最短路径的一种算法（是一确定点到其他点的最短路径），按照***最短路径长度从小到大的顺序***找到每个点的最短路径。

主要思想是这样的：假设有一点集Q（其中包含的点都是找到最短路径的点），图中部分点都在该点集中。A源点到点集之外一点B之间的最短路径只存在如下两种情况：1，最短路径就是A-B，路径长度就是AB两点之间的权值。2，点集中某一点（假设为C）充当了“中转点”的作用，最短路径是A——C-B（‘A-C’不代表从AC这条边，其中或许还需要走过其他边，‘C-B’意思是CB这条边）。

除此之外不存在其他情况，可以用反证法来证明。假设A与B之间的最短路径经过了点集Q之外的一点，记为D。则说明存在一条终点不在Q中的最短路径（A——D），其长度必小于（A——B），但是这是不可能的！因为最短路径长度是从小到大找出的。

一些必要的辅助数组

bool s[Maxvexnum]; //从源点到终点是否已经确定最短路径 int D[Maxvexnum]; //从源点到终点的最短路径长度 int path[Maxvexnum];//源点到终点最短路径上终点的直接前驱

算法的c++描述

//**这部分就是按照从小到大的顺序找出所有点（除了源点）最小路径长度** for (int i = 1; i < g.arcnum; i++) int v; int min = MaxInt; for (int j = 0; j < g.arcnum; j++) if (!s[j] && min > D[j]) { v = j; min = D[j]; } s[v] = true; //**对D[]更新，判断新加入点集Q的点是哪一种情况找出的** for (int j = 0; j < g.arcnum; j++) if (!s[j] && D[j] > D[v] + g.arcs[v][j]) { D[j] = D[v] + g.arcs[v][j]; path[j] = v; }

源代码

//目前做到能对某一点到源点的最短路径 #include<iostream> #define Maxvexnum 40 #define MaxInt 10000 static int node = 0; using namespace std; typedef char vertextype; typedef int arctype; typedef struct { vertextype vexs[Maxvexnum]; arctype arcs[Maxvexnum][Maxvexnum]; int vexnum, arcnum; }AM_Graph; bool s[Maxvexnum]; //从源点到终点是否已经确定最短路径 int D[Maxvexnum]; //从源点到终点的最短路径长度 int path[Maxvexnum];//源点到终点最短路径上终点的直接前驱 int LocateVex_AM(AM_Graph& g, char vex); void CreateGraph_AM(AM_Graph& g); void Dijkstra(AM_Graph& g, char vex); void print(AM_Graph&g, int v, int vex, int*); int LocateVex_AM(AM_Graph& g, char vex)//vs比较奇怪 { for (int i = 0; i < g.vexnum; i++) if (g.vexs[i] == vex) { return i; break; } } void CreateGraph_AM(AM_Graph& g) { cout << "输入图的总顶点数，总边数" << endl; cin >> g.vexnum >> g.arcnum; for (int i = 0; i < g.vexnum; i++) for (int j = 0; j < g.vexnum; j++) g.arcs[i][j] = MaxInt; for (int i = 0; i < g.vexnum; i++) { cout << "输入第" << i + 1 << "个顶点" << endl; cin >> g.vexs[i]; } for (int i = 0; i < g.arcnum; i++) { int cost; char v1, v2; int a, b; cout << "输入第" << i + 1 << "条边，及其权值" << endl; cin >> v1 >> v2 >> cost; a = LocateVex_AM(g, v1); b = LocateVex_AM(g, v2); g.arcs[a][b] = cost; g.arcs[b][a] = g.arcs[a][b]; } } void Dijkstra(AM_Graph& g, char vex) { int* array = new int[g.vexnum]; //保存每个点的最短路径 /*-----------------初始化------------------------*/ int a = LocateVex_AM(g, vex); for (int i = 0; i < g.vexnum; i++) { D[i] = g.arcs[i][a]; s[i] = false; if (D[i] < MaxInt) path[i] = a; else path[i] = -1; } s[a] = true; D[a] = 0; /*--------------------------------------------*/ for (int i = 1; i < g.vexnum; i++) { int v; int min = MaxInt; for (int j = 0; j < g.vexnum; j++) if (!s[j] && min > D[j]) { v = j; min = D[j]; } s[v] = true; for (int j = 0; j < g.vexnum; j++) if (!s[j] && (D[j] > D[v] + g.arcs[v][j])) { D[j] = D[v] + g.arcs[v][j]; path[j] = v; } } /**************************输出最短路径****************************/ for (int i = 0; i < g.vexnum; i++) { if (i == a)//首先排除<两个点是同一个点：源点>这种情况 cout << g.vexs[i] << "与源点是同一个点，不存在最短路径" << endl; else { cout <<"源点到"<< g.vexs[i] << "的最短路径为：" << endl; cout << g.vexs[i] << endl; //存储数组初始化 for (int k = 0; k < g.vexnum; k++) array[k] = a; print(g, i, a, array); //for (int k = 0; k < g.vexnum; k++) //cout << "！！！" << array[k] << endl; if (s[i]) { int length = g.vexnum; do//例如：array[g.vexnum]={7,3,5,2,0,0,0,0,0,0,};把后五个多余的0删除掉 { length--; } while (array[length] == array[length - 1]); for (int j = length; j >=0; j--) cout << g.vexs[array[j]] << " " << endl; cout << g.vexs[i] << endl; } else cout << "与源点不存在最短路径" << endl; } node = 0;//置零 } } void print(AM_Graph&g, int point, int source,int *array)//相当于做了个递归 { int a = path[point]; if (point == source)//递归结束 cout << " ########### " << endl; else if (a == -1)//point不具有前驱结点 cout << "该点不存在最短路径" << endl; else { array[node]=a; node++; cout << g.vexs[a] << endl; print(g, a, source, array); } } int main() { AM_Graph g; CreateGraph_AM(g); Dijkstra(g, 'a'); }

在这里面把点的前驱通过递归的方式存储在一个数组里面了

还用到了一个全局变量node，用来存贮数组下标，每个点找到最短路径之后需要把node置零。

帮助1 帮助2 帮助3