今天给各位分享c语言最短路径题的知识，其中也会对C++最短路径进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
1、街区最短路径问题 c语言2、C语言最短路径3、C语言实现最短路问题的算法4、c语言最短路径问题。5、最短路径算法 C语言
街区最短路径问题 c语言
int T,n,i,x[21],y[21],a,b,d=0,h=0,mind,minh;
或者把d=0;h=0;放到for(i=0;in;i++)前一行
C语言最短路径
int main()
{
int G[100][100] = {};
//一个记录图的邻接矩阵
int a, b, w;
//输入一共有7条边, 5个点
int i, j, k;
for(i = 1;i = 5;i++)
for(j = 1;j = 5;j++)
G[i][j] = 9999999;
for(i = 1;i = 7;i++)
{
scanf(“%d %d %d”, a, b, w);//输入每条边的信息，a和b代表这条边的两个顶点w代表两个点的距离
G[a][b] = w;
G[b][a] = w;
}
for(k = 1;k = 5;k++)
for(i = 1;i = 5;i++)
for(j = 1;j = 5;j++)
if(G[i][j] G[i][k] + G[k][j])
G[i][j] = G[i][k] + G[k][j];
printf(“%d”, G[1][4]);//输出两点之间的最短路，这里的两个点是3和5
return 0;
}
G[i][j]代表i到j的距离，甲，乙，丙，丁，戊用1，2，3，4，5代替
如果你还不懂的话，就看一些关于图论的问题，这个最短路是图论中的一个经典题
C语言实现最短路问题的算法
＃i ncludestdio.h
＃i nclude stdlib.h
//Dijkstra算法实现函数
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
int i;
int j;
int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值
int *s ;//定义具有最短路径的节点子集s
s = (int *)malloc(sizeof(int) * n);
//初始化最小路径代价和前一跳节点值
for (i = 1; i = n; i++)
{
dist[i] = cost[v][i];
s[i] = 0;
if (dist[i] == maxint)
{
prev[i] = 0;
}
else
{
prev[i] = v;
}
}
dist[v] = 0;
s[v] = 1;//源节点作为最初的s子集
for (i = 1; i n; i++)
{
int temp = maxint;
int u = v;
//加入具有最小代价的邻居节点到s子集
for (j = 1; j = n; j++)
{
if ((!s[j]) (dist[j] temp))
{
u = j;
temp = dist[j];
}
}
s[u] = 1;
//计算加入新的节点后，更新路径使得其产生代价最短
for (j = 1; j = n; j++)
{
if ((!s[j]) (cost[u][j] maxint))
{
int newdist = dist[u] + cost[u][j];
if (newdist dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
//展示最佳路径函数
void ShowPath(int n,int v,int u,int *dist,int *prev)
{
int j = 0;
int w = u;
int count = 0;
int *way ;
way=(int *)malloc(sizeof(int)*(n+1));
//回溯路径
while (w != v)
{
count++;
way[count] = prev[w];
w = prev[w];
}
//输出路径
printf(“the best path is:\n”);
for (j = count; j = 1; j–)
{
printf(“%d – “,way[j]);
}
printf(“%d\n”,u);
}
//主函数，主要做输入输出工作
void main()
{
int i,j,t;
int n,v,u;
int **cost;//代价矩阵
int *dist;//最短路径代价
int *prev;//前一跳节点空间
printf(“please input the node number: “);
scanf(“%d”,n);
printf(“please input the cost status:\n”);
cost=(int **)malloc(sizeof(int)*(n+1));
for (i = 1; i = n; i++)
{
cost[i]=(int *)malloc(sizeof(int)*(n+1));
}
//输入代价矩阵
for (j = 1; j = n; j++)
{
for (t = 1; t = n; t++)
{
scanf(“%d”,cost[j][t]);
}
}
dist = (int *)malloc(sizeof(int)*n);
prev = (int *)malloc(sizeof(int)*n);
printf(“please input the source node: “);
scanf(“%d”,v);
//调用dijkstra算法
Dijkstra(n, v, dist, prev, cost);
printf(“*****************************\n”);
printf(“have confirm the best path\n”);
printf(“*****************************\n”);
for(i = 1; i = n ; i++)
{
if(i!=v)
{
printf(“the distance cost from node %d to node %d is %d\n”,v,i,dist[i]);
printf(“the pre-node of node %d is node %d \n”,i,prev[i]);
ShowPath(n,v,i, dist, prev);
}
}
}
c语言最短路径问题。
#include stdio.h
#define N 7 /* 顶点数目 */
#define I 999 /* 表示无穷大 */
int graph[N][N] = { /* 图的邻接矩阵 */
{I, 4, 5, 8, I, I, I},
{I, I, I, 6, 6, I, I},
{I, I, I, 5, I, 7, I},
{I, I, I, I, 8, 9, 9},
{I, I, I, I, I, I, 5},
{I, I, I, I, I, I, 4},
{I, I, I, I, I, I, I}
};
int List[N]; /* 存放拓扑序列 */
int TopologicalOrder(); /* 拓扑排序函数 */
void main() /* 主 函 数 */
{
int i, j, k, l;
int ee[N], el[N]; /* 最长最短距离 */
int path_e[N][N], path_l[N][N], n_e[N], n_l[N]; /* 记录路径数据 */
/* 初始化数据 */
for (i = 0; i N; i++) {
n_e[i] = 0; /* 到 i 的最短路线的结点数 */
n_l[i] = 0; /* 到 i 的最长路线的结点数 */
ee[i] = I;
el[i] = 0;
}
ee[0] = el[0] = 0; /* 初始化头结点 */
path_e[0][0] = 0;
path_l[0][0] = 0;
n_e[0] = 1;
n_l[0] = 1;
/* 拓扑排序 */
if (!TopologicalOrder())
return;
/* 对于拓扑序列,运用动态规划步步算出最长路线与最短路线 */
for (i = 0; i N; i++) {
/* 提取拓扑序列的元素 */
k = List[i];
/* 更新它所指向顶点的所有数据 */
for (j = 0; j N; j++) {
/* 寻找指向的顶点 */
if (graph[k][j] != I) {
/* 如果新路径更短 */
if (graph[k][j] + ee[k] ee[j]) {
/* 更新最短路径长度 */
ee[j] = graph[k][j] + ee[k];
/* 更新最短路线 */
for (l = 0; l n_e[k]; l++) {
path_e[j][l] = path_e[k][l];
}
path_e[j][l] = j;
n_e[j] = l + 1;
}
/* 如果新路径更长 */
if (graph[k][j] + el[k] el[j]) {
/* 更新最长路径长度 */
el[j] = graph[k][j] + el[k];
/* 更新最长路线 */
for (l = 0; l n_l[k]; l++) {
path_l[j][l] = path_l[k][l];
}
path_l[j][l] = j;
n_l[j] = l + 1;
}
}
}
}
/* 输出结果到屏幕 */
for (i = 0; i N; i++) {
printf(“shortest(%d): %2d Path: “, i + 1, ee[i]);
for (j = 0; j n_e[i]; j++) {
printf(“%d “, path_e[i][j] + 1);
}
printf(“\n”);
printf(“longest (%d): %2d Path: “, i + 1, el[i]);
for (j = 0; j n_l[i]; j++) {
printf(“%d “, path_l[i][j] + 1);
}
printf(“\n”);
}
}
int TopologicalOrder()
{
int i, j, top, count;
int indegree[N], Stack[N];
top = 0; /* 栈顶标志 */
for (i = 0; i N; i++) {
indegree[i] = 0; /* 初始化入度 */
for (j = 0; j N; j++) {
if (graph[j][i] != I) { /* 如连通 */
indegree[i]++; /* 入度自增1 */
}
}
if (!indegree[i]){ /* 如入度为零 */
Stack[top++] = i; /* 入栈 */
}
}
count = 0; /* 输出顶点数 */
while (top != 0) {
i = Stack[–top];
List[count++] = i;
for (j = 0; j N; j++) {
if (graph[i][j] != I) { /* 如连通 */
if (!(–indegree[j])) { /* 而且入度为零 */
Stack[top++] = j; /* 入栈 */
}
}
}/* for */
}/* while */
return (count N) ? 0 : 1;
}
最短路径算法 C语言
#include stdio.h
#define MAXNODE 108
int path[MAXNODE + 1][MAXNODE + 1] = {0};
int main(void)
{
FILE *fpr, *fpw;
int va, vb, i, j, k;
fpr = fopen(“in.txt”, “r”); /* 读取的文件名称in.txt */
fpw = fopen(“out.txt”, “w”); /* path的数据在out.txt中展现 */
while (fscanf(fpr, “%d%d”, va, vb) != EOF)
path[va][vb] = path[vb][va] = 1;
for (k = 1; k = MAXNODE; ++k) {
for (i = 1; i = MAXNODE; ++i) {
for (j = 1; j = MAXNODE; ++j) {
if (!path[i][k] || !path[k][j])
continue;
if (!path[i][j])
path[i][j] = path[i][k] + path[k][j];
else if (path[i][j] path[i][k] + path[k][j])
path[i][j] = path[i][k] + path[k][j];
}
}
}
for (i = 1; i = MAXNODE; ++i) {
for (j = 1; j = MAXNODE; ++j) {
if (i == j)
fprintf(fpw, “%-10d”, 0);
else if (path[i][j])
fprintf(fpw, “%-10d”, path[i][j]);
else
fprintf(fpw, “%-10d”, -1);
}
fprintf(fpw, “\n”);
}
return 0;
}
注意：floyd算法中k为最外层，这是动态规划的思想，不能改变i,j,k的顺序！！！
这是之前的答案的错误之处。
-1表示不通。
具体程序分析，我可以加你QQ，愿意的话，你把QQ写给我。
c语言最短路径题的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于C++最短路径、c语言最短路径题的信息别忘了在本站进行查找喔。
微信扫一扫 
支付宝扫一扫 
