前言 

Nobody can go back and start a new beginning,but anyone can start today and make a new ending. 

Name:Willam  

Time:2017/3/8

1、最短路径问题介绍

问题解释： 

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径

解决问题的算法：


迪杰斯特拉算法（Dijkstra算法）
弗洛伊德算法（Floyd算法）
SPFA算法


这篇博客，我们就对Dijkstra算法来做一个详细的介绍



2、Dijkstra算法介绍


算法特点：

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
算法的思路

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。 

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点， 

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。  

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。  




3、Dijkstra算法示例演示

下面我求下图，从顶点v1到其他各个顶点的最短路径



首先第一步，我们先声明一个dis数组，该数组初始化的值为： 



我们的顶点集T的初始化为：T={v1}

既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。 

为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果： 



因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图： 



然后，继续从dis中选择未确定的顶点的值中选择一个最小的值，发现dis[3]的值是最小的，所以把v4加入到集合T中，此时集合T={v1,v3,v5,v4},然后，考虑v4的出度是否会影响我们的数组dis的值，v4有一条出度：< v4,v6>,然后我们发现：v1–v5–v4–v6的长度为：60，而dis[5]的值为90，所以我们要更新dis[5]的值，更新后的dis数组如下图： 



然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下： 



因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

起点  终点    最短路径    长度
v1    v2     无          ∞    
      v3     {v1,v3}    10
      v4     {v1,v5,v4}  50
      v5     {v1,v5}    30
      v6     {v1，v5,v4,v6} 60




4、Dijkstra算法的代码实现（c++）


Dijkstra.h文件的代码




/************************************************************/
/*                程序作者：Willam                          */
/*                程序完成时间：2017/3/8                    */
/*                有任何问题请联系：2930526477@qq.com       */
/************************************************************/
//@尽量写出完美的程序

#pragma once
//#pragma once是一个比较常用的C/C++杂注，
//只要在头文件的最开始加入这条杂注，
//就能够保证头文件只被编译一次。

#include<iostream>
#include<string>
using namespace std;

/*
本程序是使用Dijkstra算法实现求解最短路径的问题
采用的邻接矩阵来存储图
*/
//记录起点到每个顶点的最短路径的信息
struct Dis {
    string path;
    int value;
    bool visit;
    Dis() {
        visit = false;
        value = 0;
        path = "";
    }
};

class Graph_DG {
private:
    int vexnum;   //图的顶点个数
    int edge;     //图的边数
    int **arc;   //邻接矩阵
    Dis * dis;   //记录各个顶点最短路径的信息
public:
    //构造函数
    Graph_DG(int vexnum, int edge);
    //析构函数
    ~Graph_DG();
    // 判断我们每次输入的的边的信息是否合法
    //顶点从1开始编号
    bool check_edge_value(int start, int end, int weight);
    //创建图
    void createGraph();
    //打印邻接矩阵
    void print();
    //求最短路径
    void Dijkstra(int begin);
    //打印最短路径
    void print_path(int);
};



Dijkstra.cpp文件的代码




#include"Dijkstra.h"

//构造函数
Graph_DG::Graph_DG(int vexnum, int edge) {
    //初始化顶点数和边数
    this->vexnum = vexnum;
    this->edge = edge;
    //为邻接矩阵开辟空间和赋初值
    arc = new int*[this->vexnum];
    dis = new Dis[this->vexnum];
    for (int i = 0; i < this->vexnum; i++) {
        arc[i] = new int[this->vexnum];
        for (int k = 0; k < this->vexnum; k++) {
            //邻接矩阵初始化为无穷大
                arc[i][k] = INT_MAX;
        }
    }
}
//析构函数
Graph_DG::~Graph_DG() {
    delete[] dis;
    for (int i = 0; i < this->vexnum; i++) {
        delete this->arc[i];
    }
    delete arc;
}

// 判断我们每次输入的的边的信息是否合法
//顶点从1开始编号
bool Graph_DG::check_edge_value(int start, int end, int weight) {
    if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
        return false;
    }
    return true;
}

void Graph_DG::createGraph() {
    cout << "请输入每条边的起点和终点（顶点编号从1开始）以及其权重" << endl;
    int start;
    int end;
    int weight;
    int count = 0;
    while (count != this->edge) {
        cin >> start >> end >> weight;
        //首先判断边的信息是否合法
        while (!this->check_edge_value(start, end, weight)) {
            cout << "输入的边的信息不合法，请重新输入" << endl;
            cin >> start >> end >> weight;
        }
        //对邻接矩阵对应上的点赋值
        arc[start - 1][end - 1] = weight;
        //无向图添加上这行代码
        //arc[end - 1][start - 1] = weight;
        ++count;
    }
}

void Graph_DG::print() {
    cout << "图的邻接矩阵为：" << endl;
    int count_row = 0; //打印行的标签
    int count_col = 0; //打印列的标签
    //开始打印
    while (count_row != this->vexnum) {
        count_col = 0;
        while (count_col != this->vexnum) {
            if (arc[count_row][count_col] == INT_MAX)
                cout << "∞" << " ";
            else
            cout << arc[count_row][count_col] << " ";
            ++count_col;
        }
        cout << endl;
        ++count_row;
    }
}
void Graph_DG::Dijkstra(int begin){
    //首先初始化我们的dis数组
    int i;
    for (i = 0; i < this->vexnum; i++) {
        //设置当前的路径
        dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
        dis[i].value = arc[begin - 1][i];
    }
    //设置起点的到起点的路径为0
    dis[begin - 1].value = 0;
    dis[begin - 1].visit = true;

    int count = 1;
    //计算剩余的顶点的最短路径（剩余this->vexnum-1个顶点）
    while (count != this->vexnum) {
        //temp用于保存当前dis数组中最小的那个下标
        //min记录的当前的最小值
        int temp=0;
        int min = INT_MAX;
        for (i = 0; i < this->vexnum; i++) {
            if (!dis[i].visit && dis[i].value<min) {
                min = dis[i].value;
                temp = i;
            }
        }
        //cout << temp + 1 << "  "<<min << endl;
        //把temp对应的顶点加入到已经找到的最短路径的集合中
        dis[temp].visit = true;
        ++count;
        for (i = 0; i < this->vexnum; i++) {
            //注意这里的条件arc[temp][i]!=INT_MAX必须加，不然会出现溢出，从而造成程序异常
            if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
                //如果新得到的边可以影响其他为访问的顶点，那就就更新它的最短路径和长度
                dis[i].value = dis[temp].value + arc[temp][i];
                dis[i].path = dis[temp].path + "-->v" + to_string(i + 1);
            }
        }
    }

}
void Graph_DG::print_path(int begin) {
    string str;
    str = "v" + to_string(begin);
    cout << "以"<<str<<"为起点的图的最短路径为：" << endl;
    for (int i = 0; i != this->vexnum; i++) {
        if(dis[i].value!=INT_MAX)
        cout << dis[i].path << "=" << dis[i].value << endl;
        else {
            cout << dis[i].path << "是无最短路径的" << endl;
        }
    }
}


main.cpp文件的代码




#include"Dijkstra.h"


//检验输入边数和顶点数的值是否有效，可以自己推算为啥：
//顶点数和边数的关系是：((Vexnum*(Vexnum - 1)) / 2) < edge
bool check(int Vexnum, int edge) {
    if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
        return false;
    return true;
}
int main() {
    int vexnum; int edge;

    cout << "输入图的顶点个数和边的条数：" << endl;
    cin >> vexnum >> edge;
    while (!check(vexnum, edge)) {
        cout << "输入的数值不合法，请重新输入" << endl;
        cin >> vexnum >> edge;
    }
    Graph_DG graph(vexnum, edge);
    graph.createGraph();
    graph.print();
    graph.Dijkstra(1);
    graph.print_path(1);
    system("pause");
    return 0;
}

输入：



6 8
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 6 60
5 4 20

输出： 



从输出可以看出，程序的结果和我们之前手动计算的结果是一样的。

      在带权图中，把一个顶点从v0到图中任意一个顶点vi的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路几个长度最短的那条路径称为最短路径。

带权有向图的最短路径分为两类 ：

（1）单源最短路径，即求图中某一个顶点到其他各个顶点的最短路径。

（2）求每对顶点间的最短路径

（----可能有人看完者定义就受不了了，什么东西-----）

看下图，你要去学校，有如下路线，假设权值为路程，你肯定会走第三条，因为路程最短；假设权值为所花费人民币，你仍有可能选择，第三条，因为花钱少。



你是不觉得这有啥bb的，看下图假如你要从南宁去哈尔滨，你就不能一下找到最短路径。这就是研究这个问题的意义的价值。比如实时交通陆路线，工程中的修桥架线等都有用到。



一、迪杰特斯拉算法（求单源最短路径算法）

     求带权有向图某个源点到其余各个顶点的最短路径。常用Dijksta算法。

先来看实例

对下图用该算法，求从顶点1到其余顶点的最短路径



接着看下图


			
顶点
			
			

			
第1轮
			
			

			
第2轮
			
			

			
第3轮
			
			

			
第4轮
			
		

			
2
			
			

			
10

			
v1->v2
			
			

			
8

			
v1->v5->v2
			
			

			
8

			
v1->v5->v2
			
			

			
 
			
		

			
3
			
			

			
∞
			
			

			
14

			
v1->v5->v3
			
			

			
13

			
v1->v5->v4->v3
			
			

			
9

			
v1->v5->v2->v3
			
		

			
4
			
			

			
∞
			
			

			
7

			
v1->v5->v4
			
			

			
 
			
			

			
 
			
		

			
5
			
			

			
5

			
v1->v5
			
			

			
 
			
			

			
 
			
			

			
 
			
		

			
集合S
			
			

			
{1,5}
			
			

			
{1,5,4}
			
			

			
{1,5,4,2}
			
			

			
{1,5,4,2,3}
			
		
初始，从v1出发，

第一轮：检测v1与其余各个顶点的当前路程，v1要到v3,v4不可直接到达即为∞，到v2距离为10，到v5距离为5 ，选出v1->v5

第二轮：检测与v5其余各个顶点的当前路程，v1->v5->2 为8，v1->v5->v3为14，v1->v5->v4为7，选出v1->v5->v4

第三轮：检测与v4其余各个顶点的当前路程，v1->v5->v2为8，v1->v5->v4->v3为13，选出v1->v5->v2

第四轮：检测与v4其余各个顶点的当前路程，v1->v5->v2为8，v1->v5->v4->v3为13，选出v1->v5->v2->v3

再来看这该死的过程

算法步骤；(1)初始化，集合S[]初始为{0},dist[i]=arcs[0][i],i=1,2,3...

                  (2)从顶点集合V-S出发，满足dist的初始值dist[j]=Min{dist[i] | vi∈V-S}，vj 就是当前求得的一条从v0出发的最短路径的                         终点， 令S=S∪{j}

               （3）修改从v0出发到集合V-S上任一顶点vk可达的最短路径：若dist[j]+arcs[j][k]<dist[k],则令dist[k]=dist[j]+arcs[j][k]。

               （4）重复（2）（3）操作共n-1次，直到所有顶点都包含在S中。

做个例题：

求出下图从顶点1到其他各个顶点的最短路径




			
顶点
			
			

			
第1轮
			
			

			
第2轮
			
			

			
第3轮
			
			

			
第4轮
			
			

			
第5轮
			
		

			
2
			
			

			
5

			
v1->v2
			
			

			
5

			
v1->v2
			
			

			
 
			
			

			
 
			
			

			
 
			
		

			
3
			
			

			
∞
			
			

			
∞
			
			

			
7

			
v1->v2->v3
			
			

			
 
			
			

			
 
			
		

			
4
			
			

			
∞
			
			

			
11

			
v1->v5->v4
			
			

			
11

			
v1->v5->v4
			
			

			
11

			
v1->v5->v4
			
			

			
11

			
v1->v5->v4
			
		

			
5
			
			

			
4

			
v1->v5
			
			

			
 
			
			

			
 
			
			

			
 
			
			

			
 
			
		

			
6
			
			

			
∞
			
			

			
9

			
v1->v5->v6
			
			

			
9

			
v1->v5->v6
			
			

			
9

			
v1->v5->v6
			
			

			
 
			
		

			
集合S
			
			

			
{1,5}
			
			

			
{1,5,2}
			
			

			
{1,5,2,3}
			
			

			
{1,5,2,3,6}
			
			

			
{1,5,2,3,6,
			
		


这个表从第一列第一个往下开始看，直到该列完成。再从下一列第一个往下看，依次看。

第一轮从1出发可以直接到达的是1和5，写上路径和值，其余写无穷；

第一轮选出最短，得到v1->v5,所以v5加入集合S{1，5}

第二轮，把上一轮得到结果的平移抄过去，已经加入集合S的不用抄。现在从5开始判断，5能到达2距离为6，现在的v1->v5->v2为10相比上一轮的v1->v2为5，所以那个为止仍取原来的。

无论1还是5都不能直达3，所以写无穷。对于4，上一轮无法直达，现在5可直达4，此条路径v1->v5->v4为11。

因为结点5已经在集合S中，所以此处为空。

之前无法直达6，现在5可直达6，v1->v5->6为9。所以第二轮中选出最短的，得到v2加入集合S

{1，5，2}

第三轮：因为2已经在集合中，所以此处为空。因为2可直达3，v1->v2->v3为7，比原来的无穷小所以此处写v1->v2->v3

因为5可直达4，v1->v5->v4为11，相比之前的11一样，所以此处仍为v1->v5->v4

因为5已经在集合中，此处为空。

因为5能直达6，和上一轮一样9，此处仍为 v1->v5->v6

所以第三轮，选出最短v1->v2->v3，将3加入集合S 有{1，5，2，3}

第四轮：因为2，3已在集合中，所以对应位置为空。看从3出发，能否得到更短的结果，不能。再看4，2可到4 ，v1->v2->v4为14，5可到4，v1->v5->v4为11 所以此处仍为v1->v5->v4

因为5在集合中，所以此处为空。

再看6，5可直达6，v1->v5->v6为9

第四轮选出最短为9，将6加入集合S， 得到{1，5，2，3，6}

第五轮：2，3已在集合中对应为空。此时达到4的最短为v1->v5->v4。5，6已在几何中，对应位置为空。

第五轮选出最小，将4加入集合 得到

{1，5，2，3，6，4}

————————————————————————————————————————————————————————

注：当边上有负权值,迪杰特斯拉算法不再适用。

二、Floyd求各顶点之间最短路径

求各顶点之间最短路径：已知一个各边权值均大于0的带权有向图，对每对顶点，要求找出vi与vj之间的最短路径和最短路径长度。

还是来看题，



上图为一个带权有向图，及其邻接矩阵.如下为执行过程。



如图，

写出,和



接着写出A(1)和Path(1) ,将第一行和第一列全copy过来，检测经过顶点1能否改善各顶点间的路径长度

若比原来短，则更改对应位置值，否则保留原来的值。

例如，之前3->2的路径值为5，经过1为3->1->2的路径值为4，更改为4

之前，2->4路径值为2，经过1为2->1->4的路径值为4为5，仍保留2.

路径值更新的地方，对应的Path中对应位置值更改为同一列中的第一行的值



接着写出A(2)和Path(2) ,将第二行和第二列copy过来，检测经过顶点2能否改善各顶点间的路径长度



 

最短路径：

在一个带权图中，顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径最短的那条路径称为最短路径。

DiskStra算法：

求单源最短路径，即求一个顶点到任意顶点的最短路径，其时间复杂度为O(V*V)



如图所示：求顶点0到各顶点之间的最短路径

代码实现：

#include<stdio.h>
#include<stdlib.h>
#define MaxVexNum 50
#define MaxInt 32767
#define MaxEdgeNum 50
//邻接矩阵
typedef int VertexType;
typedef int EdgeType;
typedef struct AMGraph{
	VertexType vexs[MaxVexNum];//顶点表 
	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
	int vexnum,edgenum;//顶点数，边数 
}AMGraph; 

void createGraph(AMGraph &g){//创建无向图 
	printf("请输入顶点数：");
	scanf("%d",&g.vexnum);
	printf("\n请输入边数：");
	scanf("%d",&g.edgenum);
	
	//初始化顶点表 
	for(int i=0;i<g.vexnum;i++){
		g.vexs[i]=i; 
	} 
	for(int i=0;i<g.vexnum;i++){
		for(int j=0;j<g.vexnum;j++){
			g.arcs[i][j]=MaxInt;
			if(i==j) g.arcs[i][j]=0;
		}
	} 
	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
	for(int i=0;i<g.edgenum;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		g.arcs[x][y]=w;
		//g.arcs[y][x]=w;
	}
}
void PrintGraph(AMGraph g){
	printf("邻接矩阵为:\n");
	for(int i=0;i<g.vexnum;i++) {
		printf("  %d",g.vexs[i]);
	}
	printf("\n");
	for(int i=0;i<g.vexnum;i++){
		printf("%d ",g.vexs[i]);
		for(int j=0;j<g.vexnum;j++){
			if(g.arcs[i][j]==32767){
				printf("∞ "); 
			}else{
				printf("%d  ",g.arcs[i][j]);
			}	
		}
		printf("\n");
	} 
}
//Dijkstra算法，求单源最短路径
void Dijkstra(AMGraph g,int dist[],int path[],int v0){
	int n=g.vexnum,v;
	int set[n];//set数组用于记录该顶点是否归并 
	//第一步：初始化 
	for(int i=0;i<n;i++){
		set[i]=0;
		dist[i]=g.arcs[v0][i];
		if(dist[i]<MaxInt){//若距离小于MaxInt说明两点之间有路可通 
			path[i]=v0;//则更新路径i的前驱为v 
		}else{
			path[i]=-1; //表示这两点之间没有边
		 } 
	}
	set[v0]=1;//将初始顶点并入 
	path[v0]=-1;//初始顶点没有前驱
	
	//第二步 
	for(int i=1;i<n;i++){//共n-1个顶点 
		int min=MaxInt;
		//第二步：从i=1开始依次选一个距离顶点的最近顶点 
		for(int j=0;j<n;j++){
			if(set[j]==0&&dist[j]<min){
				v=j;
				min=dist[j];
		}
	}
	//将顶点并入 
	set[v]=1;	
	//第三步：在将新结点并入后，其初始顶点v0到各顶点的距离将会发生变化，所以需要更新dist[]数组
	for(int j=0;j<n;j++){
		if(set[j]==0&&dist[v]+g.arcs[v][j]<dist[j]){
			dist[j]=dist[v]+g.arcs[v][j];
			path[j]=v;
		}
	} 	
 } 
 //输出 
 printf("       ");
 for(int i=0;i<n;i++) printf("%d  ",i);
  
 printf("\ndist[]:");
 for(int i=0;i<n;i++) printf("%d  ",dist[i]);
 
 printf("\npath[]:");
 for(int i=0;i<n;i++) printf("%d  ",path[i]);

}

int main(){
	AMGraph g;
	createGraph(g);
	int dist[g.vexnum];
	int path[g.vexnum];
	Dijkstra(g,dist,path,0);
} 



Floyd算法：

求各顶点之间的最短路径,其时间复杂度为O(V*V*V)



如图所示，求<1,0>之间的最短路径：

代码实现：

#include<stdio.h>
#include<stdlib.h>
#define MaxVexNum 50
#define MaxInt 32767
#define MaxEdgeNum 50
//邻接矩阵
typedef int VertexType;
typedef int EdgeType;
typedef struct AMGraph{
	VertexType vexs[MaxVexNum];//顶点表 
	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
	int vexnum,edgenum;//顶点数，边数 
}AMGraph; 

void createGraph(AMGraph &g){//创建无向图 
	printf("请输入顶点数：");
	scanf("%d",&g.vexnum);
	printf("\n请输入边数：");
	scanf("%d",&g.edgenum);
	
	//初始化顶点表 
	for(int i=0;i<g.vexnum;i++){
		g.vexs[i]=i; 
	} 
	for(int i=0;i<g.vexnum;i++){
		for(int j=0;j<g.vexnum;j++){
			g.arcs[i][j]=MaxInt;
			if(i==j) g.arcs[i][j]=0;
		}
	} 
	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
	for(int i=0;i<g.edgenum;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		g.arcs[x][y]=w;
		//g.arcs[y][x]=w;
	}
}
void PrintGraph(AMGraph g){
	printf("邻接矩阵为:\n");
	for(int i=0;i<g.vexnum;i++) {
		printf("  %d",g.vexs[i]);
	}
	printf("\n");
	for(int i=0;i<g.vexnum;i++){
		printf("%d ",g.vexs[i]);
		for(int j=0;j<g.vexnum;j++){
			if(g.arcs[i][j]==32767){
				printf("∞ "); 
			}else{
				printf("%d  ",g.arcs[i][j]);
			}	
		}
		printf("\n");
	} 
}

//Floyd算法

//递归输出两个顶点直接最短路径 
void printPath(int u,int v,int path[][MaxVexNum]){
	if(path[u][v]==-1){
		printf("[%d %d] ",u,v);
	}else{
		int mid=path[u][v];
		printPath(u,mid,path);
		printPath(mid,v,path);
	}
}
void Floyd(AMGraph g,int path[][MaxVexNum]){
	int n=g.vexnum;
	int A[n][n];
	//第一步：初始化path[][]和A[][]数组 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			A[i][j]=g.arcs[i][j];
			path[i][j]=-1; 
		}
	}
	//第二步：三重循环，寻找最短路径 
	for(int v=0;v<n;v++){//第一层是代表中间结点 
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(A[i][j]>A[i][v]+A[v][j]){
					A[i][j]=A[i][v]+A[v][j];
					path[i][j]=v;
				}
			}
		} 
	} 
} 
 
int main(){
	AMGraph g;
	createGraph(g);
	PrintGraph(g);
	int path[MaxVexNum][MaxVexNum];
	Floyd(g,path);

	printPath(1,0,path);
} 

代码运行截图：

首先介绍这三个概念，很多人都听过最短路径了，但是最短路径树却很少听过，关于最短路径树的介绍也不太多。而最短路径树和最小生成树更是完全不同的两个概念。

       最短路径就是从一个指定的顶点出发，计算从该顶点出发到其他所有顶点的最短路径。通常用Dijkstra算法，Floyd算法求解。

       最短路径树SPT（Short Path Tree）是网络的源点到所有结点的最短路径构成的树。

       最小生成树是用和最少的边集将一个图连成任意2点可达，并且这个边集的总长度最小。保证整个拓扑图的所有路径之和最小。通常用Prim算法和kruskal算法求解。



       下面是最短路径树和最小生成树的对比图，原图来论文[1]。

原图：



对比图：

                           

                                                          最短路径树图                                    

 

 

     

                                                                      最小生成树图

        最短路径树的路径总长度为75，最小生成树的路径总长度为67.

 

最小生成树算法：

Prim方法

设N=(V,{E})是连通网，TE是N上最小生成树中边的集合：

（1）初始令U={u0},(u0属于V), TE=NULL

（2）在所有u属于U,v属于V-U的边(u,v)属于E中，找一条代价最小的边(u0,v0)

（3）将(u0,v0)并入集合TE，同时v0并入U

（4）重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树


Kruskal算法

设连通网N=(V,{E})，令最小生成树

（1）初始状态为只有n个顶点而无边的非连通图T=(V,{NULL})，每个顶点自成一个连通分量

（2）在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边

（3）依此类推，直至T中所有顶点都在同一连通分量上为止



 

最短路径算法：

最短路径：路径上所有边的权值之和最小。

某顶点到其它个点的最短路径

Dijkstra算法：

（1）初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值

（2）若存在<V0,Vi>，为<V0,Vi>弧上的权值

（3）若不存在<V0,Vi>，为无穷

（4）从T中选取一个其距离值为最小的顶点W，加入S

（5）对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值

（6）重复上述步骤，直到S中包含所有顶点，即S=V为止



每对顶点之间的最短路径

Floyd算法：

（1）初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为无穷

（2）逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值

（3）所有顶点试探完毕，算法结束