数据结构（四）—— 图（3）：最短路径问题_大彤小忆的博客-程序员资料
数据结构系列内容的学习目录 → \rightarrow →浙大版数据结构学习系列内容汇总。
3. 最短路径问题
3.1 最短路径问题的抽象
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径：
⋄ \diamond ⋄ 这条路径就是两点之间的最短路径（shortestPath)
⋄ \diamond ⋄ 第一个顶点为源点（Source)
⋄ \diamond ⋄ 最后一个顶点为终点(Destination)
3.2 问题分类
单源最短路径问题： 从某固定源点出发，求其到所有其他顶点的最短路径。
⋄ \diamond ⋄ (有向）无权图
⋄ \diamond ⋄ (有向）有权图
多源最短路径问题： 求任意两顶点间的最短路径。
3.3 单源最短路算法
3.3.1 无权图的单源最短路算法
按照递增（非递减）的顺序找出各个顶点的最短路。
在数据结构（四）图 —— 编程作业 02 ：Saving James Bond中，James Bond从孤岛跳上岸，最少需要跳多少步?
可以使用BFS算法计算！
BFS算法的代码如下所示。
void BFS(Vertex S)
{
visited[S] = true ;
Enqueue (S, Q);
while(!IsEmpty(Q)){
V = Dequeue (Q);
for (V的每个邻接点W)
if (!visited[W]){
visited[W] = true;
Enqueue (W, Q);
}
}
}
dist[W] = S到W的最短距离
dist[S] = 0
path[W] = S到W的路上经过的某顶点
无权图的单源最短路算法的代码如下所示。
void Unweighted(Vertex S){
Enqueue (S, Q);
while(!IsEmpty(Q)){
V = Dequeue (Q);
for(V的每个临界点W)
if (dist[W] == -1){
dist[W] = dist[V] + 1; // 当前距离上一距离+1
path[W] = V; // S到W的必经顶点就是前一个顶点V
Enqueue (W, Q);
}
}
}
时间复杂度为 T = O ( ∣ V ∣ + ∣ E ∣ ) T=O(|V|+|E|) T=O(∣V∣+∣E∣)。
3.3.2 有权图的单源最短路算法
按照递增的顺序找出各个顶点的最短路。
Dijkstra算法： 1. 令S={源点s ＋已经确定了最短路径的顶点 v i v_{i} vi}；
2. 对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度，但该路径仅经过S中的顶点。即路径{ s→( v i ∈ S v_{i}∈S vi∈S)→v }的最小长度；
3. 若路径是按照递增（非递减)的顺序生成的，则
⋄ \diamond ⋄ 真正的最短路必须只经过S中的顶点（为什么?)
⋄ \diamond ⋄ 每次从未收录的顶点中选一个dist最小的收录（贪心)
⋄ \diamond ⋄ 增加一个v进入S，可能影响另外一个w的dist值!
∘ \circ ∘ dist[w] = min{dist[w], dist[v] +<v ,w>的权重}
有权图的单源最短路算法的代码如下所示。
void Dijkstra(Vrtex s)
{
while (1){
V = 未收录顶点中dist最小者;
if (这样的V不存在)
break;
collected[V] == true;
for (V的每个邻接点W)
if (collected[W]== false)
if (dist[V]+E<v,w> < dist[W])
{
dist[W] = dist[V]+ E<v,w>;
path[W] = V;
}
}
}
/*不能解决有负边的情况*/
■ 方法1： 直接扫描所有未收录顶点—— O ( ∣ V ∣ ) O(|V|) O(∣V∣)
⋆ \star ⋆ T = O ( ∣ V ∣ 2 + ∣ E ∣ ) T=O(|V|^{2}+|E|) T=O(∣V∣2+∣E∣)
⋆ \star ⋆ 对于稠密图效果好
■ 方法2： 将dist存在最小堆中—— O ( l o g ∣ V ∣ ) O( log|V|) O(log∣V∣)
⋆ \star ⋆ 更新dist[w]的值—— O ( l o g ∣ V ∣ ) O( log|V|) O(log∣V∣)
⋆ \star ⋆ T = O ( ∣ V ∣ l o g ∣ V ∣ ＋ ∣ E ∣ l o g ∣ V ∣ ) = O ( ∣ E ∣ I o g ∣ V ∣ ) T= O(|V| log|V|＋|E|log|V|)=O(|E| Iog|V|) T=O(∣V∣log∣V∣＋∣E∣log∣V∣)=O(∣E∣Iog∣V∣)
⋆ \star ⋆ 对于稀疏图效果好
Dijkstra算法的步骤：
- step1：初始化所有dist为 ∞ \infty ∞，初始化所有path为-1；
- step2：从顶点 v 1 v_{1} v1开始，寻找邻接点，更新 v 2 v_{2} v2和 v 4 v_{4} v4的dist和path；
- step3：找到与 v 1 v_{1} v1最近的邻接点（即dist最小） v 4 v_{4} v4，标记collected[ v 4 v_{4} v4]=true，并对 v 4 v_{4} v4继续寻找邻接点，更新 v 3 v_{3} v3、 v 5 v_{5} v5、 v 6 v_{6} v6和 v 7 v_{7} v7的dist和path；
- step4：继续在未收录定点中寻找dist最小的顶点 v 2 v_{2} v2，标记collected[ v 2 v_{2} v2]=true，并对 v 2 v_{2} v2继续寻找邻接点，对于 v 2 v_{2} v2的邻接点 v 5 v_{5} v5，若以 v 2 v_{2} v2为前一个顶点，dist[ v 5 v_{5} v5]=2+10=12>3，所以不更新 v 5 v_{5} v5的dist和path；
- step5：继续在未收录定点中寻找dist最小的顶点 v 3 v_{3} v3，标记collected[ v 3 v_{3} v3]=true，并对 v 3 v_{3} v3继续寻找邻接点，对于 v 3 v_{3} v3的邻接点 v 6 v_{6} v6，由于若以 v 3 v_{3} v3为前一个顶点，dist[ v 6 v_{6} v6]=3+5=8<9，所以更新 v 6 v_{6} v6的dist和path；
- step6：继续在未收录定点中寻找dist最小的顶点 v 5 v_{5} v5，标记collected[ v 5 v_{5} v5]=true，并对 v 5 v_{5} v5继续寻找邻接点，对于 v 5 v_{5} v5的邻接点 v 7 v_{7} v7，若以 v 5 v_{5} v5为前一个顶点，dist[ v 7 v_{7} v7]=3+6=9>5，所以不更新 v 7 v_{7} v7的dist和path；
- step7：继续在未收录定点中寻找dist最小的顶点 v 7 v_{7} v7，标记collected[ v 7 v_{7} v7]=true，并对 v 7 v_{7} v7继续寻找邻接点，对于 v 7 v_{7} v7的邻接点 v 6 v_{6} v6，若以 v 7 v_{7} v7为前一个顶点，dist[ v 6 v_{6} v6]=5+1=6<8，所以更新 v 6 v_{6} v6的dist和path；
- step8：继续在未收录定点中寻找dist最小的顶点 v 6 v_{6} v6，标记collected[ v 6 v_{6} v6]=true， v 6 v_{6} v6没有邻接点，退出循环；
- step9：从源点 v 1 v_{1} v1到终点 v 6 v_{6} v6的最短路径：先通过 v 6 v_{6} v6找到 v 7 v_{7} v7，再通过 v 7 v_{7} v7找到 v 4 v_{4} v4，然后通过 v 4 v_{4} v4找到 v 1 v_{1} v1，所以得到最短路径 v 1 → v 4 → v 7 → v 6 v_{1} \rightarrow v_{4} \rightarrow v_{7}\rightarrow v_{6} v1→v4→v7→v6。
3.4 多源最短路算法
■ 方法1： 直接将单源最短路算法调用|V|遍
⋆ \star ⋆ T = O ( ∣ V ∣ 3 + ∣ E ∣ × ∣ V ∣ ) T=O(|V|^{3}+|E|×|V|) T=O(∣V∣3+∣E∣×∣V∣)
⋆ \star ⋆ 对于稀疏图效果好
■ 方法2： Floyd算法
⋆ \star ⋆ T = O ( ∣ V ∣ 3 ) T=O(|V|^{3}) T=O(∣V∣3)
⋆ \star ⋆ 对于稠密图效果好
Floyd算法： 1. D k [ i ] [ j ] D^{k}[i][j] Dk[i][j]=路径 { i → l ≤ k → j } \{i→ {l\leq k }→j\} {
i→l≤k→j}的最小长度
2. D 0 , D 1 , . . . . . . , D ∣ V ∣ − 1 [ i ] [ j ] D^{0}, D^{1}, ...... ,D^{|V|-1}[i][j] D0,D1,......,D∣V∣−1[i][j]，即给出了 i i i到 j j j的真正最短距离
3. 最初的 D − 1 D^{-1} D−1是什么?
4. 当 D k − 1 D^{k-1} Dk−1已经完成，递推到 D k D^{k} Dk时：
⋄ \diamond ⋄ 或者 k ∉ k\notin k∈/最短路径 { i → l ≤ k → j } \{i→ {l\leq k }→j\} {
i→l≤k→j}，则 D k = D k − 1 D^{k}= D^{k-1} Dk=Dk−1
⋄ \diamond ⋄ 或者 k ∈ k\in k∈最短路径 { i → l ≤ k → j } \{i→ {l\leq k }→j\} {
i→l≤k→j}，则该路径必定由两段最短路径组成： D k [ i ] [ j ] = D k − 1 [ i ] [ k ] + D k − 1 [ k ] [ j ] D^{k}[i][j]=D^{k-1}[i][k]+D^{k-1}[k][j] Dk[i][j]=Dk−1[i][k]+Dk−1[k][j]
多源最短路算法的代码如下所示。
void Floyd()
{
for (i = 0; i < N; i++)
for(j = 0; j < N; j++)
{
D[i][i] = G[i][j];
path[i][k]= -1;
}
for(k = 0; k < N; k++)
for(i = 0 ; i < N; i++)
for(j = 0; j < N; j++)
if( D[i][k] + D[k][j] < D[i][j])
{
D[i][j] = D[i][k] + D[k][j];
path[i][j] = k;
}
}
算法的时间复杂度为 T = O ( ∣ V ∣ 3 ) T=O(|V|^{3}) T=O(∣V∣3)。
3.5 最短路算法的实现
3.5.1 单源最短路算法的实现
3.5.1.1 无权图的单源最短路算法
对于图1所示的无权图，使用无权图的单源最短路算法找出源点3到各顶点之间的最短路，代码如下所示。
#include<iostream>
using namespace std;
/* 邻接矩阵储存——无权图的单源最短路算法 */
#define INFINITY 65535 // ∞设为双字节无符号整数的最大值65535
#define MaxVertexNum 100 //最大顶点数设为100
typedef int Vertex; //用顶点下标表示顶点,为整型
typedef int WeightType; //边的权值设为整型
#define ERROR 0
int Visited[MaxVertexNum];
int dist[MaxVertexNum];
int path[MaxVertexNum];
// 边的定义
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; // 有向边<V1, V2>
};
typedef PtrToENode Edge;
// 图结点的定义
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; // 顶点数
int Ne; // 边数
WeightType G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
};
typedef PtrToGNode MGraph; // 以邻接矩阵存储的图类型
struct Node {
int Data;
struct Node *Next;
};
struct QNode {
struct Node *rear;
struct Node *front;
};
typedef struct QNode *Queue;
// 初始化一个有VertexNum个顶点但没有边的图
MGraph CreateGraph(int VertexNum)
{
Vertex V, W;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode)); // 建立图
Graph->Nv = VertexNum;
Graph->Ne = 0;
/* 初始化邻接矩阵 */
/* 注意：这里顶点编号从0开始，到(Graph->Nv) */
for (V = 0; V <= Graph->Nv; V++)
for (W = 0; W <= Graph->Nv; W++)
Graph->G[V][W] = INFINITY;
return Graph;
}
void InsertEdge(MGraph Graph, Edge E)
{
/* 插入边 <V1, V2> */
Graph->G[E->V1][E->V2] = 1;
/* 若是无向图，还要插入边<V2, V1> */
//Graph->G[E->V2][E->V1] = 1;
}
MGraph BuildGraph()
{
MGraph Graph;
Edge E;
Vertex V;
int Nv, i;
cin >> Nv; // 读入顶点数
Graph = CreateGraph(Nv); // 初始化有Nv个顶点但没有边的图
cin >> (Graph->Ne); // 读入边数
if (Graph->Ne != 0) // 如果有边
{
E = (Edge)malloc(sizeof(struct ENode)); // 建立边结点
for (i = 0; i < Graph->Ne; i++)
{
cin >> E->V1 >> E->V2;// 读入边，格式为"起点 终点"，插入邻接矩阵
InsertEdge(Graph, E);
}
}
return Graph;
}
int IsEmpty(Queue Q)
{
return(Q->front == NULL);
};
Queue CreateQueue()
{
Queue PtrQ;
PtrQ = (Queue)malloc(sizeof(struct QNode));
struct Node *rear;
struct Node *front;
rear = (Node*)malloc(sizeof(struct Node));
rear = NULL;
front = (Node*)malloc(sizeof(struct Node));
front = NULL;
PtrQ->front = front;
PtrQ->rear = rear;
return PtrQ;
};
int DeleteQ(Queue PtrQ)
{
struct Node *FrontCell;
int FrontElem;
if (IsEmpty(PtrQ))
{
cout << "队列空" << endl;
return ERROR;
}
FrontCell = PtrQ->front;
if (PtrQ->front == PtrQ->rear)
PtrQ->front = PtrQ->rear = NULL;
else {
PtrQ->front = PtrQ->front->Next;
}
FrontElem = FrontCell->Data;
free(FrontCell);
return FrontElem;
}
void InsertQ(int item, Queue PtrQ)
{
struct Node *FrontCell;
FrontCell = (Node*)malloc(sizeof(struct Node));
FrontCell->Data = item;
FrontCell->Next = NULL;
if (IsEmpty(PtrQ))
{
PtrQ->front = FrontCell;
PtrQ->rear = FrontCell;
}
else {
PtrQ->rear->Next = FrontCell;
PtrQ->rear = FrontCell;
}
};
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。 */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下: */
bool IsEdge(MGraph Graph, Vertex V, Vertex W)
{
return Graph->G[V][W] < INFINITY ? true : false;
}
// 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索
void Unweighted(MGraph Graph, Vertex S)
{
// dist[]和path[]为全局变量，已经初始化为-1
Queue Q = CreateQueue(); // 创建空队列, MaxSize为外部定义的常数
Vertex V, W;
// 访问顶点S
dist[S] = 0; // 标记S已访问
InsertQ(S, Q); // S入队列
while (!IsEmpty(Q))
{
V = DeleteQ(Q); // 弹出V
for (W = 1; W <= Graph->Nv; W++) // 对V的每个邻接点W->AdjV
if ((dist[W] == -1) && (IsEdge(Graph, V, W))) // 若W->AdjV未被访问
{
dist[W] = dist[V] + 1;
cout << "点" << W << "到源点" << S << "的最短距离是：" << dist[W];
// 访问顶点W
path[W] = V;
cout << " 其上一个节点是：" << path[W] << endl;
InsertQ(W, Q); // W入队列
}
} /* while结束*/
}
int main()
{
MGraph Graph = BuildGraph();
for (int i = 1; i <= MaxVertexNum; i++)
{
Visited[i] = false;
dist[i] = path[i] = -1;
}
Unweighted(Graph, 3);
system("pause");
return 0;
}
图1所示的无权图使用单源最短路算法找出源点3到各顶点之间的最短路的测试效果如下图所示。
3.5.1.2 有权图的单源最短路算法
对于图2所示的有权图，使用有权图的单源最短路算法找出源点1到各顶点之间的最短路，代码如下所示。
#include<iostream>
using namespace std;
/* 邻接矩阵储存——有权图的单源最短路算法 */
#define ERROR 0
#define INFINITY 65535 // ∞设为双字节无符号整数的最大值65535
#define MaxVertexNum 100 //最大顶点数设为100
typedef int Vertex; //用顶点下标表示顶点,为整型
typedef int WeightType; //边的权值设为整型
int Visited[MaxVertexNum];
int dist[MaxVertexNum];
int path[MaxVertexNum];
// 边的定义
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; // 有向边<V1, V2>
WeightType Weight; // 权重
};
typedef PtrToENode Edge;
// 图结点的定义
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; // 顶点数
int Ne; // 边数
WeightType G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
};
typedef PtrToGNode MGraph; // 以邻接矩阵存储的图类型
// 初始化一个有VertexNum个顶点但没有边的图
MGraph CreateGraph(int VertexNum)
{
Vertex V, W;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode)); // 建立图
Graph->Nv = VertexNum;
Graph->Ne = 0;
/* 初始化邻接矩阵 */
/* 注意：这里顶点编号从0开始，到(Graph->Nv) */
for (V = 0; V <= Graph->Nv; V++)
for (W = 0; W <= Graph->Nv; W++)
Graph->G[V][W] = INFINITY;
return Graph;
}
void InsertEdge(MGraph Graph, Edge E)
{
/* 插入边 <V1, V2> */
Graph->G[E->V1][E->V2] = E->Weight;
/* 若是无向图，还要插入边<V2, V1> */
//Graph->G[E->V2][E->V1] = 1;
}
// 建图
MGraph BuildGraph()
{
MGraph Graph;
Edge E;
Vertex V;
int Nv, i;
cin >> Nv; // 读入顶点数
Graph = CreateGraph(Nv); // 初始化有Nv个顶点但没有边的图
cin >>(Graph->Ne); // 读入边数
if (Graph->Ne != 0) // 如果有边
{
E = (Edge)malloc(sizeof(struct ENode)); // 建立边结点
for (i = 0; i < Graph->Ne; i++)
{
cin >> E->V1 >> E->V2 >> E->Weight;// 读入边，格式为"起点 终点 权重"，插入邻接矩阵
InsertEdge(Graph, E);
}
}
return Graph;
}
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。 */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下: */
bool IsEdge(MGraph Graph, Vertex V, Vertex W)
{
return Graph->G[V][W] < INFINITY ? true : false;
}
// 返回未被收录顶点中的最小dist者
Vertex FindMinDist(MGraph Graph)
{
Vertex MinV, V;
int MinDist = INFINITY;
for (V = 1; V <= Graph->Nv; V++)
{
if (Visited[V] == false && dist[V] < MinDist) // 若V未被收录，且dist[V]更小
{
MinDist = dist[V]; // 更新最小距离
MinV = V; // 更新最小顶点
}
}
if (MinDist < INFINITY) // 若找到最小dist
return MinV; // 返回对应的顶点下标
else return ERROR; // 若这样的顶点不存在，返回错误标记
}
// 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索
bool Dijkstra(MGraph Graph, Vertex S)
{
Vertex V, W;
// 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示
for (V = 1; V <= Graph->Nv; V++)
{
dist[V] = Graph->G[S][V];
if (dist[V] < INFINITY)
path[V] = S;
else
path[V] = -1;
Visited[V] = false;
}
// 先将起点收入集合
dist[S] = 0;
Visited[S] = true;
while (1)
{
// 找到未被收入顶点中dist最小者
V = FindMinDist(Graph);
if (V == ERROR) // 若这样的V不存在
break; //算法结束
Visited[V] = true; //收录V
for (W = 1; W <= Graph->Nv; W++) //对图中每个顶点W
if (Visited[W] == false && Graph->G[V][W] < INFINITY) //若W未被收录并且是V的邻接点
{
if (Graph->G[V][W] < 0) //若有负边
return false; //不能正确解决，返回错误标记
if (dist[V] + Graph->G[V][W] < dist[W]) //若收录V使得dist[W]变小
{
dist[W] = dist[V] + Graph->G[V][W]; //更新dist[W]
path[W] = V; //更新S到W的路径
}
}
}/*while结束*/
return true; //算法执行完毕，返回正确标记
}
int main()
{
MGraph Graph = BuildGraph();
for (int i = 1; i <= MaxVertexNum; i++)
{
Visited[i] = false;
dist[i] = INFINITY;
path[i] = -1;
}
Dijkstra(Graph, 1);
for (int i = 1; i <= Graph->Nv; i++)
{
cout << "点" << i << "到源点1的最短距离是：" << dist[i] << " 上一步结点是：" << path[i] << endl;
}
system("pause");
return 0;
}
图2所示的有权图使用单源最短路算法找出源点1到各顶点之间的最短路的测试效果如下图所示。
3.5.2 多源最短路算法的实现
对于图3所示的有权图，使用多源最短路算法找出任意两个顶点之间的最短路，代码如下所示。
#include<iostream>
using namespace std;
/* 邻接矩阵储存——多源最短路算法 */
#define INFINITY 65535 // ∞设为双字节无符号整数的最大值65535
#define MaxVertexNum 100 //最大顶点数设为100
typedef int Vertex; //用顶点下标表示顶点,为整型
typedef int WeightType; //边的权值设为整型
// 图结点的定义
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; // 顶点数
int Ne; // 边数
WeightType G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
};
typedef PtrToGNode MGraph; // 以邻接矩阵存储的图类型
//边的数据结构
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; // 有向边<V1, V2>
WeightType Weight; // 权重
};
typedef PtrToENode Edge;
// 初始化一个有VertexNum个顶点但没有边的图
MGraph CreateGraph(int VertexNum)
{
Vertex V, W;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode)); // 建立图
Graph->Nv = VertexNum;
Graph->Ne = 0;
/* 初始化邻接矩阵 */
/* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
for (V = 0; V <= Graph->Nv; V++)
for (W = 0; W <= Graph->Nv; W++)
Graph->G[V][W] = INFINITY;
return Graph;
}
// 插入边
void InsertEdge(MGraph Graph, Edge E)
{
// 插入边 <V1,V2>
Graph->G[E->V1][E->V2] = E->Weight;
// 如果是无向图，还需要插入边 <V2,V1>
Graph->G[E->V2][E->V1] = E->Weight;
}
// 建图
MGraph BuildGraph()
{
MGraph Graph;
Edge E;
Vertex V;
int Nv, i;
cin >> Nv; // 读入顶点数
Graph = CreateGraph(Nv); // 初始化有Nv个顶点但没有边的图
cin >>(Graph->Ne); // 读入边数
if (Graph->Ne != 0) // 如果有边
{
E = (Edge)malloc(sizeof(struct ENode)); // 建立边结点
for (i = 0; i < Graph->Ne; i++)
{
cin >> E->V1 >> E->V2 >> E->Weight;// 读入边，格式为"起点 终点 权重"，插入邻接矩阵
InsertEdge(Graph, E);
}
}
return Graph;
}
//多源最短路径
bool Floyd(MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum])
{
Vertex i, j, k;
// 初始化
for (i = 1; i <= Graph->Nv; i++)
for (j = 1; j <= Graph->Nv; j++)
{
D[i][j] = Graph->G[i][j];
path[i][j] = -1;
}
for (k = 1; k <= Graph->Nv; k++)
for (i = 1; i <= Graph->Nv; i++)
for (j = 1; j <= Graph->Nv; j++)
if (D[i][k] + D[k][j] < D[i][j])
{
D[i][j] = D[i][k] + D[k][j];
if (i == j && D[i][j] < 0) // 若发现负值圈
return false; // 不能正确解决，返回错误标记
path[i][j] = k;
}
return true; // 算法执行完毕，返回正确标记
}
//路径的打印
void PrintPath(Vertex path[][MaxVertexNum], Vertex v1, Vertex v2)
{
cout << v2 << " ";
while (1)
{
if (path[v1][v2] != -1)
cout << path[v1][v2] << " ";
else
break;
v2 = path[v1][v2];
}
cout << v1 << endl;
}
int main()
{
MGraph Graph = BuildGraph();
WeightType Weight[MaxVertexNum][MaxVertexNum];
Vertex path[MaxVertexNum][MaxVertexNum];
Floyd(Graph, Weight, path);
cout << "请输入要查询最短路径的两个顶点：";
Vertex v1, v2;
cin >> v1 >> v2;
cout<<"最短路径为：";
PrintPath(path, v1, v2);
cout << "最短路径对应的权值为：" << Weight[v1][v2] << endl;
system("pause");
return 0;
}
图3所示的有权图使用多源最短路算法找出任意两个顶点之间的最短路的测试效果如下图所示。
智能推荐
使用事件驱动模型实现高效稳定的网络服务器程序_FishBear_move_on的博客-程序员资料
http://www.cnblogs.com/hnrainll/p/3625597.html前言事件驱动为广大的程序员所熟悉，其最为人津津乐道的是在图形化界面编程中的应用；事实上，在网络编程中事件驱动也被广泛使用，并大规模部署在高连接数高吞 吐量的服务器程序中，如 http 服务器程序、ftp 服务器程序等。相比于传统的网络编程方式，事件驱动能够极大的降低资源占用，增大服务接待能力
拓端tecdat|R语言和Stan,JAGS：用rstan,rjags建立贝叶斯多元线性回归预测选举数据_拓端研究室的博客-程序员资料
原文链接：http://tecdat.cn/?p=21978本文将介绍如何在R中用rstan和rjags做贝叶斯回归分析，R中有不少包可以用来做贝叶斯回归分析，比如最早的（同时也是参考文献和例子最多的）R2WinBUGS包。这个包会调用WinBUGS软件来拟合模型，后来的JAGS软件也使用与之类似的算法来做贝叶斯分析。然而JAGS的自由度更大，扩展性也更好。近来，STAN和它对应的R包rstan一起进入了人们的视线。STAN使用的算法与WinBUGS和JAGS不同，它改用了一种更强大的算法使它能..
Linux通过lftp访问sftp服务器_lftp 登录sftp_RayBreslin的博客-程序员资料
1.安装yum -y install lftp2.等陆实例lftp sftp://username:[email protected]:22关键：username：用户名password：密码ip：sftp服务器ip22：默认的端口号3.lftp常用的命令：ls显示远端文件列表(!ls 显示本地文件列表)。cd切换远端目录(lcd 切换本地目录)。get下载远端文件。mget下载远端文件(可以用通配符也就是 *)。pget使用多个线程来下...
FocusScope学习二： 很好的理解FocusScope的工作原理_firstfocusscope_PunCha的博客-程序员资料
http://www.codeproject.com/Articles/38507/Using-the-WPF-FocusScopeIntroductionOften, it is useful to maintain a separate focus for different parts of the user interface. For example, when yo
POJ1511 Invitation Cards [最短路,dijstra+heap,spfa]_aszxqw的博客-程序员资料
题意：给定节点数n,和边数m,边是单向边.问从1节点出发到2,3,...n 这些节点路程和从从这些节点回来到节点1的路程和最小值。思路：很显然的最短路，先以1为起点进行一次最短路，然后再将边反向一下再以1为起点进行一下最短路。这题的意义在于数据，一般的dijstra的O(N^2)显然没法过。先用dijstra+heap试试。(以前被这个heap唬到了，其实heap直接用pr
freeradius-aka配置笔记，自用_三叶星云的博客-程序员资料
Freeradius-server-2.1.11-aka 说明文档1freeradius1.1安装cd freeradius-akatar zxvf freeradius-server-2.1.11-AKA-2011-9-28.tar.gzcd f
随便推点
Vue配置TinyMCE富文本编辑器 + 图片（本地）上传到服务器_韩旭在努力的博客-程序员资料
一、TinyMCE是什么？TinyMCE是一款易用、且功能强大的所见即所得的富文本编辑器。同类程序有：UEditor、Kindeditor、Simditor、CKEditor、wangEditor、Suneditor、froala等等。我们可以先大体看一下配置完成后的样子注：博主使用的TinyMCE版本是 “tinymce”: “^4.8.2” 如果超过此版本可能会导致一些问题。首先如果想要在Vue中使用TinyMCE，我们需要准备一些什么？汉化的中文语言包：zh_CN.js下载下
我的Linux笔记_正熵的博客-程序员资料
学习目标：常用linux命令的使用 JAVAEE ：后台应用都会涉及到linux系统，应用程序的部署，运维，分布式集群，大数据，云计算虚拟机：虚拟出来的计算机 虚拟机软件：用来产生虚拟机的一个软件对服务器的管理，都是通过远程登录来进行，远程登录的常用软件有以下3款： xshell putty secureCRT —-recommend 推荐 这些软件都是基于一种通信协议来进行远程登录
SSL/TLS的Handshake过程与javax.net.ssl.SSLHandshakeException: Received fatal alert: handshake_failure异常_易生一世的博客-程序员资料
一.SSL/TLS的Handshake过程在SSL/TLS的Handshake过程中，客户端与服务器之间需要交换参数，具体过程如下：客户端提供其所支持的各种cipher suites（包含加密算法和Hash函数） 服务器从中选择自己也支持的cipher suite，并通知客户端，表明两者将以此进行数据传输 服务器同时将自己的数字证书（包括服务器名称、CA和公钥）作为标识符发给客户端 ...
C/C++内存管理（4）_lien0906的博客-程序员资料
本文将对 Linux? 程序员可以使用的内存管理技术进行概述，虽然关注的重点是 C 语言，但同样也适用于其他语言。文中将为您提供如何管理内存的细节，然后将进一步展示如何手工管理内存，如何使用引用计数或者内存池来半手工地管理内存，以及如何使用垃圾收集自动管理内存。为什么必须管理内存内存管理是计算机编程最为基本的领域之一。在很多脚本语言中，您不必担心内存是如何管理的，这并不能使得内存管
CMake构建、编译OpenCV工程_cmake opencv 会构建子版本号_桔子code的博客-程序员资料
原文链接：http://www.juzicode.com/opencv-note-cmake-project-vs-windowsOpenCV除了提供二进制包，还可以下载其源码手动编译二进制文件，不过源码中并没有提供可以直接编译的工程文件，需要借助CMake工具完成工程文件的构建。获取源码从官网opencv.org找到github链接，或者直接进入https://github.com/opencv/opencv/releases找到相应的版本，这里以4.5.3为例：在该版本下有多个发
排列计算（一维差分）模板_tr-uhpc一维差分模型_paranoidZ的博客-程序员资料
先讲一下一维差分：原数组为a[]，设差分数组为d[]，用于解决对区间的操作问题。原数组记录每个点被访问的次数，开始都为0.例如：原数组a[]区间[L,R]都加上C则可以先利用差分数组d[L]+=c,d[R+1]-=c,因为差分数组的前缀和为原数组，即可发现，区间[L,R]之间的数都加C了，因为d[R+1]-c了所以[R+1,N]之间的数没有变化例子链接：题目:排列计算来源：牛客网题目描述天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (International C..