实验三 最短路径的算法(离散数学实验报告)

最短路径的实验报告最短路径的实验报告引言：最短路径问题是图论中一个经典的问题，涉及到在一个带有权重的图中找到两个顶点之间的最短路径。

本实验旨在通过实际操作和算法分析，深入探讨最短路径算法的性能和应用。

实验设计：本次实验使用了Dijkstra算法和Floyd-Warshall算法来解决最短路径问题。

首先，我们使用Python编程语言实现了这两个算法，并对它们进行了性能测试。

然后，我们选择了几个不同规模的图进行实验，以比较这两种算法的时间复杂度和空间复杂度。

最后，我们还在实际应用中使用了最短路径算法，以验证其实用性。

实验过程：1. 实现Dijkstra算法Dijkstra算法是一种贪心算法，用于求解单源最短路径问题。

我们首先实现了该算法，并对其进行了性能测试。

在测试中，我们使用了一个包含1000个顶点和5000条边的图，记录了算法的运行时间。

结果显示，Dijkstra算法的时间复杂度为O(V^2)，其中V表示图中的顶点数。

2. 实现Floyd-Warshall算法Floyd-Warshall算法是一种动态规划算法，用于求解所有顶点对之间的最短路径。

我们在Python中实现了该算法，并对其进行了性能测试。

在测试中，我们使用了一个包含100个顶点和5000条边的图，记录了算法的运行时间。

结果显示，Floyd-Warshall算法的时间复杂度为O(V^3)，其中V表示图中的顶点数。

3. 比较两种算法通过对Dijkstra算法和Floyd-Warshall算法的性能测试，我们可以看到，Dijkstra算法在处理较大规模的图时性能更好，而Floyd-Warshall算法在处理较小规模的图时性能更好。

因此，在实际应用中，我们可以根据图的规模选择合适的算法。

4. 应用实例为了验证最短路径算法的实际应用性，我们选择了一个城市交通网络图进行实验。

我们使用了Dijkstra算法来计算两个城市之间的最短路径，并将结果与实际的驾车时间进行比较。

算法实验报告算法实验报告引言：算法是计算机科学的核心内容之一，它是解决问题的方法和步骤的描述。

算法的设计和分析是计算机科学与工程中的重要研究方向之一。

本实验旨在通过对算法的实际应用和实验验证，深入理解算法的性能和效果。

实验一：排序算法的比较在本实验中，我们将比较三种常见的排序算法：冒泡排序、插入排序和快速排序。

我们将通过对不同规模的随机数组进行排序，并记录每种算法所需的时间和比较次数，以评估它们的性能。

实验结果显示，快速排序是最快的排序算法，其时间复杂度为O(nlogn)，比较次数也相对较少。

插入排序的时间复杂度为O(n^2)，比较次数较多，但对于小规模的数组排序效果较好。

而冒泡排序的时间复杂度也为O(n^2)，但比较次数更多，效率相对较低。

实验二：图的最短路径算法在图的最短路径问题中，我们将比较Dijkstra算法和Floyd-Warshall算法的效率和准确性。

我们将使用一个带权有向图，并计算从一个顶点到其他所有顶点的最短路径。

实验结果表明，Dijkstra算法适用于单源最短路径问题，其时间复杂度为O(V^2)，其中V为顶点数。

而Floyd-Warshall算法适用于多源最短路径问题，其时间复杂度为O(V^3)。

两种算法在准确性上没有明显差异，但在处理大规模图时，Floyd-Warshall算法的效率较低。

实验三：动态规划算法动态规划是一种通过将问题分解成子问题并记录子问题的解来解决复杂问题的方法。

在本实验中，我们将比较两种动态规划算法：0-1背包问题和最长公共子序列问题。

实验结果显示，0-1背包问题的动态规划算法可以有效地找到最优解，其时间复杂度为O(nW)，其中n为物品个数，W为背包容量。

最长公共子序列问题的动态规划算法可以找到两个序列的最长公共子序列，其时间复杂度为O(mn)，其中m和n分别为两个序列的长度。

结论：通过本次实验，我们对不同算法的性能和效果有了更深入的了解。

排序算法中，快速排序是最快且效率最高的；在图的最短路径问题中，Dijkstra算法和Floyd-Warshall算法分别适用于不同的场景；动态规划算法可以解决复杂的问题，并找到最优解。

实验三最短路径的算法（离散数学实验报告）实验3：最短路径算法⼀、实验⽬的通过本实验的学习，理解Floyd（弗洛伊得）最短路径算法的思想⼆、实验内容⽤C语⾔编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点⾃动求出最短路径三、实验原理、⽅法和⼿段1、Floyd算法的原理定义：Dk[i,j] 表⽰赋权图中从结点vi出发仅通过v0，v1，┉，vk-1中的某些结点到达vj的最短路径的长度，若从vi到vj没有仅通过v0，v1，┉，vk-1 的路径，则D[i,j]=∝即D-1[i,j] 表⽰赋权图中从结点vi到vj的边的长度，若没有从结点vi到vj的边，则D[i,j]=∝D0[i,j] 表⽰赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0外没有其它结点D1[i,j] 表⽰赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0，v1外没有其它结点┉┉┉根据此定义，D k[i,j]=min{ D k-1[i,j] , D k-1[i,k-1]+D k-1[k-1,j] }定义：path[i,j]表⽰从结点vi到vj的“最短”路径上vi的后继结点四、实验要求要求输出每对结点之间的最短路径长度以及其最短路径五、实验步骤（⼀）算法描述Step 1 初始化有向图的成本邻矩阵D、路径矩阵path若从结点vi到vj有边，则D[i,j]= vi到vj的边的长度，path[i,j]= i；否则D[i,j]=∝，path[i,j]=-1Step 2 刷新D、path 对k=1,2,┉n 重复Step 3和Step 4Step 3 刷新⾏对i=1,2,┉n 重复Step 4Step 4 刷新Mij 对j=1,2,┉n若D k-1[i,k]+D k-1[k,j][结束循环][结束Step 3循环][结束Step 2循环]Step 5 退出（⼆）程序框图参考主程序框图其中，打印最短路径中间结点调⽤递归函数dist()，其框图如下，其中fist,end是当前有向边的起点和终点dist(int first, int end)七、测试⽤例：1、输⼊成本邻接矩阵：D ：06380532290141003210∝∝∝∝V V V V V V V V （其中∝可⽤某个⾜够⼤的数据值代替，⽐如100）可得最短路径矩阵：P ：131132122211111010103210--------V V V V V V V V以及各顶点之间的最短路径和最短路径长度：从V0到V1的最短路径长度为：1 ；最短路径为：V0→V1 从V0到V2的最短路径长度为：9 ；最短路径为：V0→V1→V3→V2 从V0到V3的最短路径长度为：3 ；最短路径为：V0→V1→V3 从V1到V0的最短路径长度为：11；最短路径为：V1→V3→V2→V0从V1到V2的最短路径长度为：8 ；最短路径为：V1→V3→V2 从V1到V3的最短路径长度为：2 ；最短路径为：V1→V3 从V2到V0的最短路径长度为：3 ；最短路径为：V2→V0 从V2到V1的最短路径长度为：4 ；最短路径为：V2→V0→V1 从V2到V3的最短路径长度为：6 ；最短路径为：V2→V0→V1→V3 从V3到V0的最短路径长度为：9 ；最短路径为：V3→V2→V0 从V3到V1的最短路径长度为：10；最短路径为：V3→V2→V0→V1 从V3到V2的最短路径长度为：6 ；最短路径为：V3→V2 参考程序： #include #define INFINITY 100 #define Max 10int a[Max][Max],P[Max][Max]; main() {void Print_Flod(int d);int i,j,k,D=4;printf("请输⼊成本邻接矩阵：\n");for(i=0;ifor(j=0;j{scanf("%d",&a[i][j]);}for(i=0;ifor(j=0;j{if(a[i][j]>0&& a[i][j]elseP[i][j]=-1;}for(k=0;kfor(i=0;ifor(j=0;jif (a[i][k]+a[k][j]{a[i][j]=a[i][k]+a[k][j];P[i][j]=k;}Print_Flod(D);}void Print_Flod(int d){void dist(int first,int end);int i,j;for(i=0;ifor(j=0;jif(i!=j){ printf("from V%d to V%d: ",i,j); dist(i,j);printf("V%d",j);printf(" (The length is: %d)\n",a[i][j]); }}void dist(int first,int end){ int x;x=P[first][end];if(x!=first){ dist(first,x); dist(x,end); }else printf("V%d->",x);}输出结果：。

最短路径实验报告最短路径实验报告引言：最短路径算法是计算机科学中的一个经典问题，它在许多领域中都有广泛的应用，如交通规划、电路设计、网络通信等。

本实验旨在通过实践探索最短路径算法的实际应用，并对其性能进行评估。

一、问题描述：我们将研究一个城市的交通网络，其中包含多个节点和连接这些节点的道路。

每条道路都有一个权重，表示通过该道路所需的时间或距离。

我们的目标是找到两个节点之间的最短路径，即使得路径上各个道路权重之和最小的路径。

二、算法选择：为了解决这个问题，我们选择了Dijkstra算法和Floyd-Warshall算法作为比较对象。

Dijkstra算法是一种单源最短路径算法，它通过不断选择当前最短路径的节点来逐步扩展最短路径树。

Floyd-Warshall算法则是一种多源最短路径算法，它通过动态规划的方式计算任意两个节点之间的最短路径。

三、实验设计：我们首先构建了一个包含10个节点和15条道路的交通网络，每条道路的权重随机生成。

然后，我们分别使用Dijkstra算法和Floyd-Warshall算法计算两个节点之间的最短路径，并记录计算时间。

四、实验结果：经过实验，我们发现Dijkstra算法在计算单源最短路径时表现出色，但是在计算多源最短路径时效率较低。

而Floyd-Warshall算法在计算多源最短路径时表现出色，但是对于大型网络的单源最短路径计算则需要较长的时间。

五、性能评估：为了评估算法的性能，我们对不同规模的交通网络进行了测试，并记录了算法的计算时间。

实验结果显示，随着交通网络规模的增大，Dijkstra算法的计算时间呈指数级增长，而Floyd-Warshall算法的计算时间则呈多项式级增长。

因此，在处理大型网络时，Floyd-Warshall算法具有一定的优势。

六、实际应用：最短路径算法在实际应用中有着广泛的用途。

例如，在交通规划中，最短路径算法可以帮助我们找到最优的行车路线，减少交通拥堵。

Dijkstra最短路径算法实习报告1.引言交通诱导系统的一个核心技术是最优路径的选择技术。

根据交通网络模型中各顶点和顶点之间的长度、时间或费用等属性权值，通过Dijkstra最短路径算法，解决有向图即交通网络模型中源点到其他顶点的最短路径问题。

2.建立交通道路网络模型交通道路网是路径诱导的基础和对象，首先需要建立交通道路网络模型。

交通道路网中的路段具有属性，且同一路段的两个方向其属性一般不完全相同，有向图能够很好地表达实际的交通网络，便于处理同路段两个方向的不同属性和单行线、交叉口转向限制等特殊交通属性。

综上，采用带权有向图来表达交通道路网。

其中，道路的终点和十字路口通常定义为一个顶点，两个顶点之间的道路定义为一条弧，每条弧根据其距离、途中所需时间或交通费用等定义为路段权值。

在有向图上，一条以i为起点，以j为终点的路径是一些顶点的序列，其中前一条弧的终点是后一条弧的起点，一条路线用一个有序的点集描述，而一条路线的长度、时间或者费用等属性为这条路径上的所有弧的权值之和。

这样便建立好了交通道路网络的模型。

3.最短路径算法迪杰斯特拉（Dijkstra）算法是经典路径诱导规划算法，Dijkstra算法是一个按路径长度递增的次序产生最短路径的算法，算法比较简单，容易实现，但计算量较大。

3.1算法分析：首先引进辅助向量D，它的每个分量D[i]表示当前所找到的从始点v0到每个终点vi的最短路径的长度。

为D[i]赋初值，若从v0到vi有弧，则D[i]为弧上的权值，否则置D[i]为∞。

则长度为D[j]=Min{D[i]|vi∈v}的路径就是从v0出发的长度最短的一条最短路径，此路径为v0—vj。

设下一条长度次短的路径的终点是vk，则这条路径或者是v0—vk，或者是v0—vj—vk。

它的长度是v0到vk弧上的权值或D[j]和vj到vk弧上权值之和。

3.2算法正确性证明：设s为为已切得最短路径的终点的集合，则有结论：下一条最短路径（设其终点为vx）或者是v0—vx，或者是中间只经过s中的顶点而最后到达顶点x的路径。

离散数学迷宫问题从一个迷宫的入口到出口找出一条可通路经。

用一个二维数组MG(0：M，0：N)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。

MG(1，1)和MG(M-1，N-1)分别为迷宫50输入1. 输入迷宫的大小M行和N列，两者为整数2. 给定MG[M，N]各元素的值（0或1），建立迷宫。

输出是否有通路（YES或NO）样例输入5 51 1 1 1 1 11 0 0 0 0 11 0 0 0 1 11 0 0 1 0 11 0 0 1 0 11 1 1 1 1 1样例输出NO提示1）读入两个整数M，N后，迷宫的大小是0~M和0~N，也就是实际上有M+1行和N+1列2）判断是否有通路主要是判断点（1，1）到点（M-1，N-1）之间是否有通路，第0行、第M行、第1列、第N列的所有值都一定是1。

#include "stdio.h"struct{int i;int j;int di;}stack[10000];int top=-1;int fun(){int mg[500][500],i,j,di,find,N,M,x,y;scanf("%d%d",&M,&N);for(x=0;x<=M;x++)for(y=0;y<=N;y++)scanf("%d",&mg[x][y]);top++;stack[top].i=1; stack[top].j=1; stack[top].di=-1; mg[1][1]=-1;while(top>=0){i=stack[top].i; j=stack[top].j; di=stack[top].di;if(i==M-1&&j==N-1){printf("YES\n");return 0;}find=0;while(di<4&&find==0){di++;if(di==0){i=(stack[top].i)-1; j=stack[top].j;}if(di==1){i=stack[top].i; j=(stack[top].j)+1;}if(di==2){i=(stack[top].i)+1; j=stack[top].j;}if(di==3){i=stack[top].i; j=(stack[top].j)-1;}if(mg[i][j]==0){find=1;break;}}if(find==1){stack[top].di=di;top++;stack[top].i=i; stack[top].j=j; stack[top].di=-1;mg[i][j]=-1;}else{mg[stack[top].i][stack[top].j]=1;top--;}}printf("NO\n");return 0;}int main(){fun();return 0;}。

离散数学迷宫问题问题描述：一只老鼠走进了一个迷宫，这个迷宫是由M行N列（如:10行8列）的方格构成的，相邻方格之间可能是相通的，也可能有墙相隔，各方格位置由其对应坐标确定，如图所示。

迷宫在（1，1）处有一个入口，在（M,N）处有一个出口，在入口和出口之间有通路相通。

问题是让你帮助老鼠找出从入口到出口的一条最短路径。

00001000110010100001000000001010101000000011101110001000基本要求：为老鼠找出一条从入口到出口的最短路径。

实现提示：1、迷宫用数组表示，1代表是墙走不通，0表示可以通行。

边界可以扩充为墙，即M×N 迷宫用(M+2)×(N+2)数组表示。

2、向4个方向前进时的位移量可以用以下数组表示，处理是方便。

int move[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };3、采用图的广度优先搜索算法。

#include<stdio.h>#define m 7#define n 8void path(){int maze[m+2][n+2] ;int move[4][2]={ {0,-1},{-1,0},{0,1},{1,0} };int s[54][3];int top=0;int i,j,k,f=0;int g,h,p;for(i=0;i<m+2;++i)for(j=0;j<n+2;++j)scanf("%d",&maze[i][j]);maze[1][1]=2;s[top][0]=1;s[top][1]=1;s[top][2]=0;++top;while(top!=0&&f==0){--top;i=s[top][0];j=s[top][1];k=s[top][2];while(k<4){g=i+move[k][0];h=j+move[k][1];if(g==m&&h==n&&maze[g][h]==0) {for(p=0;p<top;++p)printf("%3d,%d\n",s[p][0],s[p][1]);printf("%3d,%d\n",i,j);printf("%3d,%d\n",m,n);f=1;}//ifif(maze[g][h]==0){maze[g][h]=2;s[top][0]=i;s[top][1]=j;s[top][2]=k;++top;i=g;j=h;k=0;}//ifk=k+1;}//while}//whileif(f==0)printf("no path\n"); }//pathvoid main(){path();}。

一、实验目的学习掌握图的存储结构利用最短路径算法，通过java编程实现最短路径输出。

二、实验环境Eclipse平台三、实验过程最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。

传统的最短路径算法主要有Floyd算法和Dijkstra算法。

Floyd算法用于计算所有结点之间的最短路径。

Dijkstra算法则用于计算一个结点到其他所有结点的最短路径。

本程序利用Dijkstra算法用java语言实现最短路径的可视化。

流程: 画无向邻接矩阵邻接矩阵初始化求取最短路径Java文件如下M ain.java 文件：import java.awt.BorderLayout;import java.awt.Color;import java.awt.FlowLayout;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt.event.ItemEvent;import java.awt.event.ItemListener;import java.util.StringTokenizer;import javax.swing.JButton;import javax.swing.JComboBox;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPanel;import javax.swing.border.TitledBorder;public class Main {public static void main(String args[]) {new UI("最短路径");}}@SuppressWarnings("serial")class UI extends JFrame implements ActionListener, ItemListener { JFrame frame;JButton button;JLabel label1, label2, label3;JComboBox list1, list2;JPanel panel1, panel2;ShortCanvas canvas;ShortInit inits;SetFont f;String circlename[];String circle1, circle2;String path[];int circlenum;int list2_index;int D[];int renum[];int num = 0;UI(String s) {super(s);canvas = new ShortCanvas();add(canvas,BorderLayout.CENTER);f=new SetFont();inits = new ShortInit();circlename = inits.getcirclename();circlenum =inits.getcirclenum();circle1 = circlename[0];circle2 = circlename[0];panel2 = new JPanel();panel2.setBorder(new TitledBorder("最短路径"));panel2.setBackground(Color.white);panel2.setLayout(new FlowLayout(FlowLayout.LEADING, 5, 5));label1 = new JLabel("起点", JLabel.LEFT);label1.setFont(f.setSysFontAndFace());panel2.add(label1);list1 = new JComboBox();list1.addItemListener(this);list1.setMaximumRowCount(5);// 设置 JComboBox 显示的最大行数panel2.add(list1);label2 = new JLabel("终点");label2.setFont(f.setSysFontAndFace());panel2.add(label2);list2 = new JComboBox();list2.addItemListener(this);panel2.add(list2);list2.setMaximumRowCount(5);// 设置 JComboBox 显示的最大行数for (int i = 0; i < circlenum; i++) {list1.addItem(circlename[i]);list2.addItem(circlename[i]);}button = new JButton("确定");button.addActionListener(this);button.setFont(f.setSysFontAndFace());panel2.add(button);label3 = new JLabel("");label3.setFont(f.setSysFontAndFace());panel2.add(label3);add(panel2,BorderLayout.SOUTH);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);setBounds(100, 100, 530, 547);setVisible(true);validate();}public void itemStateChanged(ItemEvent e) {if (e.getSource() == list1)circle1 = (String) list1.getSelectedItem();if (e.getSource() == list2) {circle2 = (String) list2.getSelectedItem();list2_index = list2.getSelectedIndex();}}public void actionPerformed(ActionEvent e) {if (e.getSource() == button) {ShortPath sp = new ShortPath(circle1, circle2);path = sp.getpath();D = sp.getD();label3.setText("最短路径为:" + D[list2_index]);renum = new int[circlenum];StringTokenizer fenxi = newStringTokenizer(path[list2_index], "->");num = 0;while (fenxi.hasMoreTokens()) {String str = fenxi.nextToken();for (int i = 0; i < circlenum; i++) {if (str.equals(circlename[i])) {renum[num] = i;num++;}}}canvas.flag = 1;canvas.resultroad = renum;canvas.num = num;canvas.repaint();}}}SetFont.java文件import java.awt.Font;import javax.swing.JFrame;import javax.swing.UIManager;import javax.swing.UnsupportedLookAndFeelException;//系统外观处理@SuppressWarnings("serial")public class SetFont extends JFrame {public Font setSysFontAndFace() {try {// 根据类名称设置外观UIManager.setLookAndFeel("com.sun.java.swing.plaf.windows.WindowsLookAndFeel" );} catch (UnsupportedLookAndFeelException ex) {} catch (IllegalAccessException ex) {} catch (InstantiationException ex) {} catch (ClassNotFoundException ex) {}Font font = new Font("新宋体", Font.ITALIC + Font.BOLD, 17);return font;}}ShortCanvas.java文件://画无向邻接矩阵import java.awt.Canvas;import java.awt.Color;import java.awt.Graphics;@SuppressWarnings("serial")public class ShortCanvas extends Canvas {SetFont f;ShortInit init;String circlename[];int roadlength[];int arcs[][]; // 带权邻接矩阵int circlenum;int roadnum;int location[][]; // 各点坐标int flag = 0;int num;int resultroad[];// 结果线路ShortCanvas() {f = new SetFont();init = new ShortInit();circlename = init.getcirclename();roadlength = init.getroadlength();circlenum = init.getcirclenum();roadnum = init.getroadnum();arcs = new int[circlenum][circlenum];location = new int[circlenum][2];for (int i = 0; i < circlenum; i++)for (int j = 0; j < circlenum; j++)arcs[i][j] = 10000;set();}public void paint(Graphics g) {g.setFont(f.setSysFontAndFace());g.drawOval(60, 60, 25, 25); // ag.drawString(circlename[0], 70, 75);g.drawString(String.valueOf(roadlength[0]), 135, 135);g.drawOval(200, 180, 25, 25); // bg.drawString(circlename[1], 210, 195);g.drawLine(70, 85, 200, 192); // a--bg.drawOval(100, 300, 25, 25); // cg.drawString(circlename[2], 110, 315);g.drawString(String.valueOf(roadlength[1]), 90, 195);g.drawLine(70, 85, 112, 300); // a--cg.drawString(String.valueOf(roadlength[2]), 165, 250);g.drawLine(200, 192, 112, 300); // b--cg.drawOval(350, 180, 25, 25); // dg.drawString(circlename[3], 360, 195);g.drawString(String.valueOf(roadlength[3]), 285, 190);g.drawLine(225, 192, 350, 192); // b--dg.drawOval(250, 360, 25, 25); // gg.drawString(circlename[4], 260, 375);g.drawString(String.valueOf(roadlength[4]), 185, 345);g.drawLine(125, 315, 250, 375); // c--gg.drawString(String.valueOf(roadlength[5]), 305, 270);g.drawLine(275, 372, 350, 192); // g--dg.drawOval(450, 80, 25, 25); // eg.drawString(circlename[5], 460, 95);g.drawString(String.valueOf(roadlength[6]), 420, 150);g.drawLine(375, 192, 462, 105); // d--eg.drawOval(480, 300, 25, 25); // fg.drawString(circlename[6], 490, 315);g.drawString(String.valueOf(roadlength[7]), 465, 205);g.drawLine(462, 105, 492, 300); // e--fg.drawString(String.valueOf(roadlength[8]), 420, 280);g.drawLine(375, 192, 480, 312); // d--fg.drawString(String.valueOf(roadlength[9]), 370, 330);g.drawLine(275, 372, 480, 312); // g--fg.drawString(String.valueOf(roadlength[10]), 260, 85);g.drawLine(70, 85, 450, 92); // a--eint i, j;if (flag == 1) {g.setColor(Color.red);for (i = 0; i < num - 1; i++) {j = i + 1;g.drawLine(location[resultroad[i]][0] + 12,location[resultroad[i]][1] + 12,location[resultroad[j]][0] + 12,location[resultroad[j]][1] + 12);}}}public void set() {location[0][0] = 60;location[0][1] = 60;location[1][0] = 200;location[1][1] = 180;location[2][0] = 100;location[2][1] = 300;location[3][0] = 350;location[3][1] = 180;location[4][0] = 250;location[4][1] = 360;location[5][0] = 450;location[5][1] = 80;location[6][0] = 480;location[6][1] = 300;arcs[0][1] = arcs[1][0] = roadlength[0];arcs[0][2] = arcs[2][0] = roadlength[1];arcs[1][2] = arcs[2][1] = roadlength[2];arcs[1][3] = arcs[3][1] = roadlength[3];arcs[2][4] = arcs[4][2] = roadlength[4];arcs[4][3] = arcs[3][4] = roadlength[5];arcs[3][5] = arcs[5][3] = roadlength[6];arcs[5][6] = arcs[6][5] = roadlength[7];arcs[3][6] = arcs[6][3] = roadlength[8];arcs[4][6] = arcs[6][4] = roadlength[9];arcs[0][5] = arcs[5][0] = roadlength[10];}public int[][] getarcs() {return arcs;}}ShortInit.java文件：public class ShortInit {int circlenum=7;int roadnum=9;int num[];String circlename[];int roadlength[];ShortInit (){circlename=new String[10];roadlength=new int[15];circlename[0]="a";circlename[1]="b";circlename[2]="c";circlename[3]="d";circlename[4]="g";circlename[5]="e";circlename[6]="f";roadlength[0]=7;roadlength[1]=6;roadlength[2]=3;roadlength[3]=20;roadlength[4]=5;roadlength[5]=3;roadlength[6]=9;roadlength[7]=6;roadlength[8]=8;roadlength[9]=11;roadlength[10]=8;}public String[] getcirclename(){return circlename;}public int[] getroadlength(){return roadlength;}public int getcirclenum(){return circlenum;}public int getroadnum(){return roadnum;}}Shortpath.java 文件//求取最短路径public class ShortPath {int maxlength = 10000;int maxcirclenum = 30;ShortInit init;ShortCanvas canvas;String circlename[];String start, end;String path[];int arcs[][];int circlenum;int roadnum;int v0;int D[];ShortPath(String s1, String s2) {init = new ShortInit();canvas = new ShortCanvas();circlename = init.getcirclename();circlenum = init.getcirclenum();roadnum = init.getroadnum();start = s1;end = s2;arcs = canvas.getarcs();path = new String[circlenum];for (int p = 0; p < circlenum; p++)path[p] = start;for (int k = 0; k < circlenum; k++) {if (start.equals(circlename[k])) {v0 = k;}}shortestpath(v0);}public void shortestpath(int v0) {int v, i, w;int min;boolean finald[] = new boolean[maxcirclenum];D = new int[maxcirclenum];boolean p[][] = new boolean[maxcirclenum][maxcirclenum];for (v = 0; v < circlenum; v++) {finald[v] = false;D[v] = arcs[v0][v];for (w = 0; w < circlenum; ++w)p[v][w] = false;if (D[v] < maxlength) {p[v][v0] = true;p[v][v] = true;}}D[v0] = 0;finald[v0] = true;for (i = 1; i < circlenum; i++) {min = maxlength;for (w = 0; w < circlenum; w++)if (!finald[w])if (D[w] < min) {v = w;min = D[w];}finald[v] = true;path[v] = path[v] + "->" + circlename[v];for (w = 0; w < circlenum; w++) {if (!finald[w] && (min + arcs[v][w] < D[w])) {D[w] = min + arcs[v][w];path[w] = path[v];p[w][w] = true;}}}for (int j = 0; j < circlenum; ++j) {System.out.println(path[j] + ": "+ String.valueOf(D[j]) + "km");}}public String[] getpath() {return path;}public int[] getD() {return D;}}四、实验结果五、实验体会通过这次实验，懂得了如何通过邻接矩阵存储图，然后利用迪杰斯特拉算法算出最短路径。

离散数学实验报告离散数学实验报告一、引言离散数学是一门研究离散结构及其运算规则的数学学科，它在计算机科学、信息科学、通信工程等领域具有重要的应用价值。

本实验旨在通过实际案例，探索离散数学在现实生活中的应用。

二、实验目的本实验的目的是通过离散数学的理论知识，解决一个实际问题。

我们选择了图论中的最短路径问题作为案例，以展示离散数学在网络路由、物流规划等领域的应用。

三、实验过程1.问题描述我们的实验场景是一个城市的交通网络，其中各个交叉路口被看作是图的节点，而道路则是图的边。

我们需要找到两个给定节点之间的最短路径，以便规划出行路线。

2.建模为了解决这个问题，我们需要将实际情况抽象成数学模型。

我们将交通网络表示为一个有向图，每个节点代表一个交叉路口，每条边代表一条道路。

每条边上还需要标注距离或时间等权重。

3.算法选择在离散数学中，有多种算法可以解决最短路径问题，如迪杰斯特拉算法、弗洛伊德算法等。

根据实际情况和需求，我们选择了迪杰斯特拉算法。

4.算法实现我们使用编程语言实现了迪杰斯特拉算法，并将其应用于我们的交通网络模型。

算法的核心思想是通过不断更新节点之间的最短距离，逐步找到最短路径。

5.实验结果经过实验，我们成功找到了两个给定节点之间的最短路径，并计算出了最短距离。

这对于规划出行路线具有重要意义，可以帮助人们节省时间和资源。

四、实验总结通过这个实验，我们深入理解了离散数学在实际问题中的应用。

离散数学的概念和算法不仅仅是理论上的抽象，它们可以帮助我们解决现实生活中的复杂问题。

离散数学的应用远不止于此，它还可以用于密码学、数据压缩、人工智能等领域。

通过学习离散数学，我们能够培养出良好的抽象思维和问题解决能力，为未来的科学研究和工程实践打下坚实的基础。

总之，离散数学是一门具有广泛应用前景的学科，通过实验，我们对其应用领域有了更深入的了解。

希望未来能有更多的人关注和研究离散数学，为推动科学技术的发展做出贡献。