文章目录

一、路径的概念

二、Dijkstra算法解决单源

三、Floyd算法解决多源

一、路径的概念：

考虑带权有向图，把一条路径（仅仅考虑简单路径）上所经边的权值之和定义为该路径的路径长度或称带权路径长度


二、迪克斯特拉（Dijkstra）算法解决单源：

需要解决的带权有向图的最短路径问题：

不适合负权值：














Dijkstra算法代码实现：

#include<stdio.h>

#define maxn 2510
#define INF 999999 //无穷大 

int n,m,s,t;//n表示顶点个数，m表示边数，s表示起点，t表示终点 
int map[maxn][maxn];//用矩阵来存储图 
int visited[maxn];//记录，标记 
int dist[maxn];//最短路径 

void Dijkstra(){
   
	//初始化最短路径数组 
	for(int i=0;i<n;i++)
	dist[i]=INF;
	//起点为值0 
	dist[s]=0;
	//进行n次循环 
	for(int i=0;i<n;i++){
   
		int u=-1;int MIN=INF;
		//找出对应最短边 
		for(int j=0;j<n;j++){
   
			if(!visited[j]&&dist[j]<MIN)
			{
   
				MIN=dist[j];
				u=j;
			}
		}
		if(u==-1) break;
		visited[u]=1;
		//看第三条边是否能使路径变短，若能就换 
		for(int v=0;v<n;v++)
		{
   
			if(!visited[v]&&map[u][v]!=INF&&dist[u]+map[u][v]<dist[v])
			dist[v]=dist[u]+map[u][v];
		}
	}
}
int main()
{
   
	//输入顶点，边，起点，终点 
	scanf("%d %d %d %d",&n,&m,&s,&t);
	//初始化，
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	{
   
		if(i!=j)
		map[i][j]=INF;	
	}
	//输入每条边对应的路径长度 
	for(int i=0;i<m;i++)
	{
   
		int t1,t2,t3;
		scanf("%d %d %d",&t1,&t2,&t3);
		map[t1][t2]=map[t2][t1]=t3;
	}
	Dijkstra();
	printf("%d",dist[t]);
}

三、弗洛伊德（Floyd）算法：