目录
一、最短路径概念
二、迪杰斯特拉(Dijkstra)算法(单源最短路径)
1、原理
2、过程
3、代码
三、弗洛伊德(Floyd)算法(多源最短路径)
1、原理
2、存储
3、遍历
4、代码
参考资料
一、最短路径概念
最短路径,顾名思义,两结点之间最短的路径(可以是非邻接结点)。
最小生成树和最短路径区别:
最小生成树:连通图的最短路径。
最短路径:两任意结点之间(可以非邻接)的最短路径。
二、迪杰斯特拉(Dijkstra)算法(单源最短路径)
优点:效率较高,时间复杂度为O(n^2)。
缺点:只能求一个顶点到所有顶点的最短路径。(单源最短路)
1、原理
1、先选定一个根结点,并选定一个数组,先确定未遍历前的初始距离,把距离最短的邻接结点选定为中间结点,并标记访问过,开始往下遍历,挨个访问那个中间结点的邻接结点。计算出根结点到中间结点+中间结点到新邻接结点的距离,作为新距离,对比新距离和旧距离,如果新距离大,则把新距离替换掉旧距离,否则不变。
2、一轮访问结束后,从未标记的结点中选定距离最短的,把它作为中间结点,继续往下访问。若都标记过,则算法结束。
2、过程
1、保存根结点及到其他结点的权(距离)

2、访问最近结点作为中间结点
3、对比新距离(根结点到中间结点+中间结点到新结点)和旧距离(根结点直接到新结点)

4、若新距离短,修改保存到数组

5、继续访问后面的,把未访问的距离根最近结点作为中间结点,继续访问它的邻接结点

6、继续对比新距离和旧距离

7、若新距离短,则修改保存到数组

8、继续以距离根结点最短的结点为对象,访问它的邻接结点
9、全部访问完毕,结束算法

欣赏一下自己的稿书:
3、代码
//迪杰斯特拉(Dijkstra)算法
/*测试案例
ABCDEFGHI
B 1 C 5
A 1 C 3 D 7 E 5
A 5 B 3 E 1 F 7
B 7 E 2 G 3
B 5 C 1 F 3 H 9 G 6 D 2
C 7 E 3 H 5
D 3 E 6 H 2 I 7
F 5 E 9 G 2 I 4
G 7 H 4
*/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAXSIZE 20
#define MAX 65535//代表无穷大
int length = 0;//顶点个数
int root = 0;//根顶点
int rootDist[MAXSIZE];//根顶点(记录根到其他顶点的距离)
bool visit[MAXSIZE];//记录各结点是否访问
//图(顶点和权)
typedef struct
{
char vertex[MAXSIZE];
int weight[MAXSIZE][MAXSIZE];//权可以代替边(自身为0,相连有值,不相连无穷大)
}Graph;
Graph G;
//输入顶点
void InputVertex()
{
int i;
char ch;
printf("请输入图的顶点:\n");
scanf("%c", &ch);
for (i = 0; i < MAXSIZE && ch != '\n'; i++)
{
G.vertex[i] = ch;
scanf("%c", &ch);
}
length = i;
}
//图权重初始化
void GraphWeightInit()
{
int i, j;
for (i = 0; i < length; i++)
{
for (j = 0; j < length; j++)
{
if (i == j)//指向自己
G.weight[i][j] = 0;
else
G.weight[i][j] = MAX;//无穷大
}
}
}
//根据数据查找图顶点下标
int FindIndex(char ch)
{
int i;
for (i = 0; i < length; i++)
{
if (G.vertex[i] == ch)
return i;
}
return -1;
}
//创建图
void CreateGraph()
{
int i, j, index, weight;
char ch;