图论(最短路径,Dijkstra算法和Floyd算法)
程序员文章站
2022-04-30 09:17:59
...
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
#define maxSize 101
int INF = -2313;
int MINF = 6666;//定义图的图的无穷大量
typedef struct MGraph
{
int n,e;
int edges[maxSize][maxSize];
};
//邻接表
typedef struct ArcNode
{
int adjvex;//该点所指顶点的位置信息
ArcNode *nextarc;//指向下一条边
} ArcNode;
typedef struct
{
int data;
int count;//统计入度信息
ArcNode *firstarc;//指向第一条边
} VNode,AdjList;
typedef struct AGraph
{
AdjList adjlist[maxSize];
int n,e;
} AGraph;
int visit[1001];
//邻接矩阵转化为邻接表
void creatAGraph(AGraph *G,MGraph M)
{
G->e = M.e;
G->n = M.n;
for(int i=0; i<M.n; i++) //构造顶点表
{
G->adjlist[i].data = i;
G->adjlist[i].firstarc = NULL;
G->adjlist[i].count = 0;
}
ArcNode *p;
for(int i=0; i<M.n; i++) //头插法来构造
{
for(int j=0; j<M.n; j++)
if(M.edges[i][j]!=0)//当存在边的时候采用头插法来构造
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->adjlist[i].firstarc;
G->adjlist[i].firstarc = p;
G->adjlist[j].count++;//对应的入度加1
}
}//end for
}
void Visit(int v)
{
printf("->%d",v);
}
//Dijkstra最短路径
//单源最短路径
/*
M
v 访问的起点
dist 路径数组
path 记录该节点的前驱结点信息
*/
void Dijkstra(MGraph M,int v,int dist[],int path[])
{
int i,j,u;//u保存存放的结点信息
int vset[maxSize];//访问标记数组
int min;
//初始化
for(i=0;i<M.n;i++)
{
dist[i] = M.edges[v][i];
vset[i] = 0;//标记改结点未访问
if(M.edges[v][i] != 0)//在最短路径中的节点
path[i] = v;
else
path[i] = -1;
}//end for
path[v] = -1;
vset[v] = 1;//标记起点访问过
//对剩余n-1个结点并入最短路径中
for(i=0;i<M.n-1;i++)
{
//从当前选出最短路径
min =MINF;//重置最小值
for(j=0;j<M.n;j++)
if(vset[j] == 0&&dist[j]<min)//当该节点未访问,并且最小选出该结点将其并入最短路径中
{
min = dist[j];
u = j;
}
vset[u] = 1;//将选出当前权值最小的结点并入最短路径中
//更新path和dist
for(j=0;j<M.n;j++)
if(vset[j] ==0&&M.edges[u][j]+dist[u]<dist[j])//当以该节点作为起始结点到j的距离与dist数组作比较
{
dist[j] = dist[u] + M.edges[u][j];
path[j] = u;//记录j的在最短路径上的前驱结点为u
}
}//end for
}//end Dijkstra
//打印当前最短路径的信息
void printPath_Dijkstra(int path[],int a)
{
stack<int> S;
while(path[a] != -1)
{
S.push(a);
a = path[a];
}
S.push(a);//将根节点入栈
while(!S.empty())
{
printf("%d->",S.top());
S.pop();
}
printf("\n");
}
/*
Floyd 所有顶点的最短路径(任意两点之间的最短路径问题)
path[][]用来记录两结点之间中间结点的信息
A[][] 数组存放任意两结点之间最路径的长度
*/
void Floyd(MGraph M,int path[][maxSize],int A[][maxSize])
{
int k;//k为中间结点
int i,j;
//初始化数据
for(i=0;i<M.n;i++)
for(j=0;j<M.n;j++)
{
A[i][j] = M.edges[i][j];
path[i][j] = -1;
}
for(k=0;k<M.n;k++)//依次遍历每个中间结点
for(i=0;i<M.n;i++)
for(j=0;j<M.n;j++)
if(A[i][j]>A[i][k]+A[k][j])//当从i到j的路径长度大于经过中间结点k时则更新A[][]
{
A[i][j] = A[i][k] + A[j][k];
path[i][j] = k;
}
}//end Floyd
//输出从v到u的路径
//递归算法
void printPath_Floyd(int u,int v,int path[][maxSize])
{
if(path[u][v] == -1)//从u->v为直接的一条边,直接输出
printf("%d->%d\n",u,v);
else{
int mid = path[u][v];
printPath_Floyd(u,mid,path);//递归调用从u到mid(中间结点)
printPath_Floyd(mid,v,path);//递归调用从mid(中间结点)到v
}
}//end printPath_Floyd
推荐阅读
-
floyd最短路径算法(poj3660 cow contest)
-
Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
-
最短路弗洛伊德(Floyd)算法加保存路径
-
c/c++ 图的最短路径 Dijkstra(迪杰斯特拉)算法
-
Python使用Dijkstra算法实现求解图中最短路径距离问题详解
-
Python基于Floyd算法求解最短路径距离问题实例详解
-
python实现Dijkstra算法的最短路径问题
-
图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)
-
PHP实现的迪科斯彻(Dijkstra)最短路径算法实例
-
网络最短路径Dijkstra算法解析