最短路径(C语言, floyd算法)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最短路径(C语言, floyd算法)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5512字，纯文字阅读大概需要8分钟。

内容图文

最短路径(C语言, floyd算法) - 文章图片

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/*
 * 代码实现<<大话数据结构>>p267 图7-7-13,和dijkstra算法同一张图
 * v0至v8分别用ABCDEFGHI代替
 * 时间复杂度O(n)^3, 虽然比dijkstra O(n)^2慢，但是可以求得任意顶点间的最短路径及开销
 */

#define MAX 9
#define INFINITY 65535
typedef int NextPoint[MAX][MAX]; // 存放v到w的最短路径时要先经过的顶点,非parent关系
typedef int PathMatrix[MAX][MAX]; // 存放各顶点间的最短路径开销, D数组

// 图结构体
typedef struct {
    char vexs[MAX]; // 顶点的数组，顶点类型为了简单使用char
    int arc[MAX][MAX]; // 边表二维数组，值为权
    int numVex;
}GRAPH, *PGRAPH;

void create(PGRAPH);
void gprint(GRAPH);
void addEdge(PGRAPH, int, int, int);
void floyd(GRAPH, PathMatrix *, NextPoint *);

void floyd(GRAPH graph, PathMatrix *D, NextPoint *P)
{
    int v, w, k;

    // 初始化D, P数组
    for (v=0; v<graph.numVex; v++) {
        for (w=0; w<graph.numVex; w++) {
            (*D)[v][w] = graph.arc[v][w];
            (*P)[v][w] = w;
        }
    }

    /* 开始循环查找最短路径，更新D P数组
       k为中转顶点，用于比对是否v经过k到w的开销比D数组中当前更小
       如果更小，则说明k更有可能存在于v到w最短路径上，更新D，及P
    */
    for (k=0; k<graph.numVex; k++) {
        // v行
        for (v=0; v<graph.numVex; v++) {
            // v行所有w列 
            for (w=0; w<graph.numVex; w++) {
                // 判断k是否有可能在v和w的最短路径上
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    // 更新两点间的距离和
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w]; 
                    //因为k存在于v到w的路径上，所以v想要到w需要先经过 v到k要经过的顶点
                    (*P)[v][w] = (*P)[v][k]; 
                }
            }
        }
    }
}
void addEdge(PGRAPH g, int i, int j, int v)
{
    g->arc[i][j] = g->arc[j][i] = v;
}

void create(PGRAPH g)
{
    int i, j;

    g->numVex = 9;
    // 创建顶点
    g->vexs[0] = 'A';
    g->vexs[1] = 'B';
    g->vexs[2] = 'C';
    g->vexs[3] = 'D';
    g->vexs[4] = 'E';
    g->vexs[5] = 'F';
    g->vexs[6] = 'G';
    g->vexs[7] = 'H';
    g->vexs[8] = 'I';
    // 初始化边表矩阵
    for (i=0; i<g->numVex; i++) {
        for (j=0; j<g->numVex; j++) {
            g->arc[i][j] = INFINITY;
            if (j == i)
                g->arc[i][j] = 0; //行列相等时表示自身，标识为0
        }
    }
    // 添加边及权值
    // A v0, B v1, C v2, D v3, E v4, F v5, G v6, H v7, I, v8
    addEdge(g, 0, 1, 1);
    addEdge(g, 0, 2, 5);
    addEdge(g, 1, 2, 3);
    addEdge(g, 1, 4, 5);
    addEdge(g, 1, 3, 7);
    addEdge(g, 2, 4, 1);
    addEdge(g, 2, 5, 7);
    addEdge(g, 3, 4, 2);
    addEdge(g, 3, 6, 3);
    addEdge(g, 4, 5, 3);
    addEdge(g, 4, 7, 9);
    addEdge(g, 4, 6, 6);
    addEdge(g, 5, 7, 5);
    addEdge(g, 6, 7, 2);
    addEdge(g, 6, 8, 7);
    addEdge(g, 7, 8, 4);
}

void gprint(GRAPH graph)
{
    int i, j;
    for (i=0; i<graph.numVex; i++) {
        for (j=0; j<graph.numVex; j++){
            printf("%6d ", graph.arc[i][j]);
        }
        putchar('\n');
    }

}

int main(void)
{
    int i, j, k;
    GRAPH graph;
    NextPoint next_point;
    PathMatrix distance;

    create(&graph);
    gprint(graph);
    floyd(graph, &distance, &next_point);
    printf("D数组(任意顶点间的最短路径开销或者叫距离)\n");
    for (i=0; i<MAX; i++) {
        for (j=0; j<MAX; j++) {
            printf("%6d ", distance[i][j]);
        }
        putchar('\n');
    }
    printf("任意顶点间的最短路径:\n");
    for (i=0; i<MAX; i++) {
        for (j=i+1; j<MAX; j++) {
            printf("%d -> %d distance: %3d, path:", i, j, distance[i][j]);
            printf("%d->", i); // 先打印源点
            k = next_point[i][j];
            while (k != j) {
                printf("%d->", k);
                k = next_point[k][j]; // 相当于递归查找
            }
            printf("%d\n", k);
        }
    }

    return 0;
}

output

# gcc shortestPath_floyd.c && ./a.out
     0      1      5  65535  65535  65535  65535  65535  65535 
     1      0      3      7      5  65535  65535  65535  65535 
     5      3      0  65535      1      7  65535  65535  65535 
 65535      7  65535      0      2  65535      3  65535  65535 
 65535      5      1      2      0      3      6      9  65535 
 65535  65535      7  65535      3      0  65535      5  65535 
 65535  65535  65535      3      6  65535      0      2      7 
 65535  65535  65535  65535      9      5      2      0      4 
 65535  65535  65535  65535  65535  65535      7      4      0 
D数组(任意顶点间的最短路径开销或者叫距离)
     0      1      4      7      5      8     10     12     16 
     1      0      3      6      4      7      9     11     15 
     4      3      0      3      1      4      6      8     12 
     7      6      3      0      2      5      3      5      9 
     5      4      1      2      0      3      5      7     11 
     8      7      4      5      3      0      7      5      9 
    10      9      6      3      5      7      0      2      6 
    12     11      8      5      7      5      2      0      4 
    16     15     12      9     11      9      6      4      0 
任意顶点间的最短路径:
0 -> 1 distance:   1, path:0->1
0 -> 2 distance:   4, path:0->1->2
0 -> 3 distance:   7, path:0->1->2->4->3
0 -> 4 distance:   5, path:0->1->2->4
0 -> 5 distance:   8, path:0->1->2->4->5
0 -> 6 distance:  10, path:0->1->2->4->3->6
0 -> 7 distance:  12, path:0->1->2->4->3->6->7
0 -> 8 distance:  16, path:0->1->2->4->3->6->7->8
1 -> 2 distance:   3, path:1->2
1 -> 3 distance:   6, path:1->2->4->3
1 -> 4 distance:   4, path:1->2->4
1 -> 5 distance:   7, path:1->2->4->5
1 -> 6 distance:   9, path:1->2->4->3->6
1 -> 7 distance:  11, path:1->2->4->3->6->7
1 -> 8 distance:  15, path:1->2->4->3->6->7->8
2 -> 3 distance:   3, path:2->4->3
2 -> 4 distance:   1, path:2->4
2 -> 5 distance:   4, path:2->4->5
2 -> 6 distance:   6, path:2->4->3->6
2 -> 7 distance:   8, path:2->4->3->6->7
2 -> 8 distance:  12, path:2->4->3->6->7->8
3 -> 4 distance:   2, path:3->4
3 -> 5 distance:   5, path:3->4->5
3 -> 6 distance:   3, path:3->6
3 -> 7 distance:   5, path:3->6->7
3 -> 8 distance:   9, path:3->6->7->8
4 -> 5 distance:   3, path:4->5
4 -> 6 distance:   5, path:4->3->6
4 -> 7 distance:   7, path:4->3->6->7
4 -> 8 distance:  11, path:4->3->6->7->8
5 -> 6 distance:   7, path:5->7->6
5 -> 7 distance:   5, path:5->7
5 -> 8 distance:   9, path:5->7->8
6 -> 7 distance:   2, path:6->7
6 -> 8 distance:   6, path:6->7->8
7 -> 8 distance:   4, path:7->8

内容总结

以上是互联网集市为您收集整理的最短路径(C语言, floyd算法)全部内容，希望文章能够帮你解决最短路径(C语言, floyd算法)所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/591348.html

来源：【匿名】

【上一篇】冒泡排序、选择排序、直接插入排序、快速排序>从零开始学JAVA系列【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【最短路径(C语言, floyd算法)】教程文章相关的互联网学习教程文章

题目要求编写一个C语言程序,实现基本的冒泡排序算法.算法冒泡排序,用一句话来总结:一组数中,相邻的两个数进行比较、交换,将最大(小)数交换至尾(首)部,即完成了一次冒泡排序要想对N个数字进行排序,循环N次即可.如果真的不理解冒泡排序算法,请点击:冒泡排序_360百科核心代码//方式一:从头向尾遍历,将最大数(相对)沉入尾部(相对) void BubbleSort1(int *arr,int sz){int i = 0;int j = 0;assert(arr);for(i=0;i<sz-1;i++){for(j=0;j<s...

《数据结构与算法分析：C语言描述》复习——第六章“排序”——选择排序【代码】

2014.06.17 01:17简介：　　选择排序是一种O(n^2)级别的交换排序算法，属于新手必学算法。描述：　　个人觉得选择排序的代码是所有排序中最直观，最符合人类大脑思维的了。当我第一次有排序的需求时（初中时自学了一点C语言，算是人生第一次写代码），我自己试着写下的代码就是选择排序，当然我上了大学才知道“选择排序”是什么。很显然，直观且容易实现的算法基本都是最鹾的，而不直观且容易实现的算法基本都是最神的。很显然，选...

C语言之基本算法34—分解质因数（方法一）

//矩阵基础 /* ================================================================== 题目：输入一个正整数。将其分解为质因式，如：60=2*2*3*5；若本身是质数，则输出如：307是一个质数！ ================================================================== */ #include<stdio.h> void main() { int n,m,c,i,k,y[40]; printf("输入一个正整数："); scanf("%d",&n); while(n>0) { m=n; c=0; k=m/2; for(i=2;i<=k;i++) { while...

C语言之基本算法09—各位全是a的数列之和

/* ================================================================== 题目：数列为a,aa,aaa,……。求a+aa+aaa+……+aaaaaaa……。 ================================================================== */ #include<stdio.h> main() {int a,i,n,x,Sn,flag=1;while(flag){printf("最后一项是几位数：\nn=");scanf("%d",&n);printf("a=");scanf("%d",&a);if((a>0)&&(a<10)&&(n>0)&&(n<10))flag=0;elseprintf("系统提示：a和n都...

C语言算法设计一个算法，将数组m个元素循环右移。要求算法空间复杂度为O(1)【代码】

题目如题：数组是一个常规一维数组，直接放代码，代码讲解见注解#include<stdio.h> void swap(int a[],int i,int j) {a[i]=a[i]+a[j]-(a[j]=a[i]); } void insert(int a[],int i,int n)//插入算法，每次把第i个数放到这个数组的最后面{int key=a[i];//插入算法的核心思想和插入排序当中是一样的，设定一个key，让key插入到最后面while(i<n){a[i]=a[i+1];++i;if(i+1==n)//当i处于数组最后一位的时候，停止循环break;}a[i]=key;//在数...

关于中值滤波算法，以及C语言实现（转）【代码】

源：关于中值滤波算法，以及C语言实现1、什么是中值滤波？中值滤波是对一个滑动窗口内的诸像素灰度值排序，用其中值代替窗口中心象素的原来灰度值，它是一种非线性的图像平滑法，它对脉冲干扰级椒盐噪声的抑制效果好，在抑制随机噪声的同时能有效保护边缘少受模糊。中值滤波可以过滤尖峰脉冲。目的在于我们对于滤波后的数据更感兴趣。滤波后的数据保留的原图像的变化趋势，同时去除了尖峰脉冲对分析造成的影响。以一维信号的中...

【原创】《算法导论》链表一章带星习题试解——附C语言实现

原题：双向链表中，需要三个基本数据，一个携带具体数据，一个携带指向上一环节的prev指针，一个携带指向下一环节的next指针。请改写双向链表，仅用一个指针np实现双向链表的功能。定义np为next XOR prev，请根据表头提供的信息，为双向链表编写插入函数、删除函数和查找函数，并在O(1)时间内实现链表的翻转。分析：问题的关键，在于怎样利用prev指针和next指针的异或结果，来获得上一节点或下一节点的地址值。也就是说，如何利用...

致那些年追寻C语言编程的青春, 从语法, 到界面, 再到算法, 只有这些了【图】

那些年学C/C++的我做过这些项目，这些年正在学习的你们做过什么，纯属装逼娱乐，请勿模仿。懵懂期那时还是彩笔一个，终极版菜鸟，倒弄一些自以为很有意思的东西作品一：（效果稍微久一点）大家熟悉的黑窗口 GIF 作品二：（效果稍微久一点）大家熟悉的黑窗口其他黑窗口的东西，太多了，就不提起了，反正就是很多很多作品二：推箱子 GIF 在后面就发现自己脑智商完全跟不上了，甚至有点怀疑是不是智商不够了，想想就有点害怕，不过...

C语言排序算法学习笔记——交换类排序【代码】

交换类排序：根据序列中两个元素关键字的比较结果来交换他俩在序列中的位置。冒泡排序：假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]）则交换他们，直到序列比较完。我们称它为一趟冒泡，结果将最小的元素交换到待排序序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中最小元素放到了序列的最终位置，……，这样最多...

C语言高级程序设计——进制算法以及位算符号

语言不够官方；意会；数据储存运算是以二进制的，二进制数有原码反码补码三种。通常所说的二进制就是原码。（语言不官方）原码：4的原码可以为：0000 0100；最高位0 可以为符号数反码：正数和原码相同，负数的符号位不变，其余位0变1,1变0补码：正数和原码相同，负数的补码在反码的基础上加1（二进制存储是以补码来存的）二进制八进制互转　　　　二转八：三位转一位；八转二：一位转三位；二进制十进制互转　　　　二转十：按照...

c语言----- 冒泡排序 for while do-while 递归练习【代码】

1. 冒泡排序简介（默认从小到大排序）　核心思想：只比较相邻的两个元素，如果满足条件就交换　　 5 8 2 1 6 9 4 3 7 0目标：0 1 2 3 4 5 6 7 8 9　　第一次排序：　　5 < 8 不交换　　5 8 2 1 6 9 4 3 7 0 8 >2 满足条件交换....　　5 2 8 1 6 9 4 3 7 0　　5 2 1 8 6 9 4 3 7 0　　5 2 1 6 8 9 4 3 7 0　　5 2 1 6 8 9 4 3 7 0　　5 2 1 6 8 4 9 3 7 0　　5 2 1 6 8 4 3 9 7 0　　5 2 1 6 8 4 3 7 9 0　　5 2 1 6 8 ...

数据结构之---C语言实现线索二叉树【图】

//线索二叉树，这里在二叉树的基础上添加了线索化 //杨鑫 #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef enum {Link,Thread} childTag; //Link表示结点，Thread表示线索 typedef struct bitNode {ElemType data;struct bitNode *lchild, *rchild;int ltag, rtag; } bitNode, *bitTree;bitTree pre; //创建全局变量，表示刚刚访问过的结点/* 创建二叉树，其输入必须按照前序遍历的次序。 T...

C语言堆排序【代码】【图】

堆是一种类似二叉树的数据结构，分为最大堆和最小堆，最大堆得定义是当前节点必须大于左右子节点，堆中所有节点都要符合这个定义。最小堆反之。这一点不同于二叉树排序。假设有数组int a[10] = {90,45,21,43,22,77,13,89,56,84}，根据最大堆来初始化数组最大堆初始化代码思路：用数组最后一个元素来确定最后一个子节点，根据子节点来找到其父节点。先比较左右子节点确定最大子节点，如果父节点大于则不用互换，否则父节点与最大子节...

C语言之选择排序【图】

选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列，算法步骤是：1、从数组存放的n个数中找出最小数的下标（算法见下面的“求最值”），然后将最小数与第1个数交换位置；2、除第1个数以外，再从其余n-1个数中找出最小数（即n个数中的次小数）的下标，将此数与第2个数交换位置；3、重复步骤1 n-1趟，即可完成所求。好了，接下来看代码:#include <stdio.h> #include <stdlib.h> #define n 10 int main() { i...

每日LeetCode - 145. 二叉树的后序遍历（C语言）【代码】【图】

C语言#define NULL ((void *)0) /*** Definition for a binary tree node.*/struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right; };/*** Note: The returned array must be malloced, assume caller calls free().*/int* postorderTraversal(struct TreeNode* root, int* returnSize){int* res = (int*)malloc(sizeof(res)*501);*returnSize=0;postorder(root, res, returnSize);return res; }void postorder...

最短路径 - 相关标签

最短路径算法

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 最短路径(C语言, floyd算法)

最短路径(C语言, floyd算法)

内容导读

内容图文

内容总结

内容备注

内容手机端

【最短路径(C语言, floyd算法)】教程文章相关的互联网学习教程文章

【C语言】两种方式实现冒泡排序算法【代码】

《数据结构与算法分析：C语言描述》复习——第六章“排序”——选择排序【代码】

C语言之基本算法34—分解质因数（方法一）

C语言之基本算法09—各位全是a的数列之和

C语言算法设计一个算法，将数组m个元素循环右移。要求算法空间复杂度为O(1)【代码】

关于中值滤波算法，以及C语言实现（转）【代码】

【原创】《算法导论》链表一章带星习题试解——附C语言实现

致那些年追寻C语言编程的青春, 从语法, 到界面, 再到算法, 只有这些了【图】

C语言排序算法学习笔记——交换类排序【代码】

C语言高级程序设计——进制算法以及位算符号

c语言----- 冒泡排序 for while do-while 递归练习【代码】

数据结构之---C语言实现线索二叉树【图】

C语言堆排序【代码】【图】

C语言之选择排序【图】

每日LeetCode - 145. 二叉树的后序遍历（C语言）【代码】【图】

最短路径 - 相关标签

C语言 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程