C#实现的最短路径分析

代码如下:

using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;

namespace ConsoleApplication1
 {
     class Program
     {
         static int length = 6;
         static string[] shortedPath = new string[length];
         static int noPath = 2000;
         static int MaxSize = 1000;
         static int[,] G =
         {
             { noPath, noPath, 10, noPath, 30, 100 },
             { noPath, noPath, 5, noPath, noPath, noPath },
             { noPath, noPath, noPath, 50, noPath, noPath },
             { noPath, noPath, noPath, noPath, noPath, 10 },
             { noPath, noPath, noPath, 20, noPath, 60 },
             { noPath, noPath, noPath, noPath, noPath, noPath }
         };
         static string[] PathResult = new string[length];

static int[] path1 = new int[length];
         static int[,] path2 = new int[length, length];
         static int[] distance2 = new int[length];

static void Main(string[] args)
         {
             int dist1 = getShortedPath(G, 0, 1, path1);
             Console.WriteLine("点0到点5路径:");
             for (int i = 0; i < path1.Length; i++)
                 Console.Write(path1[i].ToString() + " "); 
             Console.WriteLine("长度:" + dist1);

Console.WriteLine("\r\n-----------------------------------------\r\n");

int[] pathdist = getShortedPath(G, 0, path2);
             Console.WriteLine("点0到任意点的路径:");
             for (int j = 0; j < pathdist.Length; j++)
             {
                 Console.WriteLine("点0到" + j + "的路径:");
                 for (int i = 0; i < length; i++)
                     Console.Write(path2[j, i].ToString() + " ");
                 Console.WriteLine("长度:" + pathdist[j]);
             }
             Console.ReadKey();

}

//从某一源点出发,找到到某一结点的最短路径
         static int getShortedPath(int[,]G, int start, int end,int [] path)
         {
             bool[] s = new bool[length]; //表示找到起始结点与当前结点间的最短路径
             int min;  //最小距离临时变量
             int curNode=0; //临时结点,记录当前正计算结点
             int[] dist = new int[length];
             int[] prev = new int[length];

//初始结点信息
             for (int v = 0; v < length; v++)
             {
                 s[v] = false;
                 dist[v] = G[start, v];
                 if (dist[v] > MaxSize)
                     prev[v] = 0;
                 else
                     prev[v] = start;
             }
             path[0] = end;
             dist[start] = 0;
             s[start] = true;
             //主循环
             for (int i = 1; i < length; i++)
             {
                 min = MaxSize;
                 for (int w = 0; w < length; w++)
                 {
                     if (!s[w] && dist[w] < min)
                     {
                         curNode = w;
                         min = dist[w];
                     }
                 }

s[curNode] = true;
                 for (int j = 0; j < length; j++)
                     if (!s[j] && min + G[curNode, j] < dist[j])
                     {
                         dist[j] = min + G[curNode, j];
                         prev[j] = curNode;
                     }

}
             //输出路径结点
             int e = end, step = 0;
             while (e != start)
             {
                 step++;
                 path[step] = prev[e];
                 e = prev[e];
             }
             for (int i = step; i > step/2; i--)
             {
                 int temp = path[step - i];
                 path[step - i] = path[i];
                 path[i] = temp;
             }
             return dist[end];
         }

//从某一源点出发,找到到所有结点的最短路径
         static int[] getShortedPath(int[,] G, int start, int[,] path)
         {
             int[] PathID = new int[length];//路径(用编号表示)
             bool[] s = new bool[length]; //表示找到起始结点与当前结点间的最短路径
             int min;  //最小距离临时变量
             int curNode = 0; //临时结点,记录当前正计算结点
             int[] dist = new int[length];
             int[] prev = new int[length];
             //初始结点信息
             for (int v = 0; v < length; v++)
             {
                 s[v] = false;
                 dist[v] = G[start, v];
                 if (dist[v] > MaxSize)
                     prev[v] = 0;
                 else
                     prev[v] = start;
                 path[v,0] = v;
             }

dist[start] = 0;
             s[start] = true;
             //主循环
             for (int i = 1; i < length; i++)
             {
                 min = MaxSize;
                 for (int w = 0; w < length; w++)
                 {
                     if (!s[w] && dist[w] < min)
                     {
                         curNode = w;
                         min = dist[w];
                     }
                 }

s[curNode] = true;

for (int j = 0; j < length; j++)
                     if (!s[j] && min + G[curNode, j] < dist[j])
                     {
                         dist[j] = min + G[curNode, j];
                         prev[j] = curNode;
                     }

}
             //输出路径结点
             for (int k = 0; k < length; k++)
             {
                 int e = k, step = 0;
                 while (e != start)
                 {
                     step++;
                     path[k, step] = prev[e];
                     e = prev[e];
                 }
                 for (int i = step; i > step / 2; i--)
                 {
                     int temp = path[k, step - i];
                     path[k, step - i] = path[k, i];
                     path[k, i] = temp;
                 }
             }
             return dist;

}

}
 }

(0)

相关推荐

  • 在SQL Server中实现最短路径搜索的解决方法

    开始这是去年的问题了,今天在整理邮件的时候才发现这个问题,感觉顶有意思的,特记录下来. 在表RelationGraph中,有三个字段(ID,Node,RelatedNode),其中Node和RelatedNode两个字段描述两个节点的连接关系:现在要求,找出从节点"p"至节点"j",最短路径(即经过的节点最少). 图1. 解析: 了能够更好的描述表RelationGraph中字段Node和 RelatedNode的关系,我在这里特意使用一个图形来描述,如图2. 图2

  • c++查询最短路径示例

    复制代码 代码如下: //shortest_path.c#include<stdio.h>#include<stdlib.h>//用file#include<string.h>//可用gets(),puts()#include"shortest_path.h"#define MAX 32767#define MENU "欢迎进入导航系统!\n==========菜单===========\n0.载入北外地图\n1.建立地图\n2.查询最短路

  • 最小生成树算法C语言代码实例

    在贪婪算法这一章提到了最小生成树的一些算法,首先是Kruskal算法,实现如下: MST.h 复制代码 代码如下: #ifndef H_MST#define H_MST #define NODE node *#define G graph *#define MST edge ** /* the undirect graph start */typedef struct _node { char data; int flag; struct _node *parent;} node; typede

  • 最小生成树算法之Prim算法

    本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程. 1.什么是最小生成树算法? 简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小.这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法. 2.Prim算法的步骤是什么? 这就要涉及一些图论的知识了. a.假定图的顶点集合为V,边集合为E. b.初始化点集合U={u}.//u为V中的任意选定的一点 c.从u的邻接结点中

  • Java实现利用广度优先遍历(BFS)计算最短路径的方法

    本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法.分享给大家供大家参考.具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点,然后计算任意两点之间的最短路径. 如下图所示: 如,我想从North Gate去Canteen, 程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Ga

  • 详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)

    1.最小生成树:无向连通图的所有生成树中有一棵边的权值总和最小的生成树 1.1 问题背景: 假设要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路.这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网.在每两个城市之间都可以设置一条线路,相应地都要付出一定的经济代价.n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条,以使总的耗费最少呢? 1.2 分析问题(建立模型): 可以用连通网来表示n个城市以及n个城市间可能设置的通信线

  • C#实现的最短路径分析

    复制代码 代码如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 {     class Program     {         static int length = 6;         static string[] shortedPath = new string[length];        

  • 使用PostGIS完成两点间的河流轨迹及流经长度的计算(推荐)

    目录 基础准备工作 1.PostGIS 的安装 2.加载Post GIS扩展 3.河流矢量图层转成单线格式 4.河流矢量数据导入PostgreSQL数据库 5.河流数据拓扑处理 PG分析处理函数 1.函数编写 2.参数说明 3.内部调用函数说明 4.输出结果验证 基础准备工作 1.PostGIS 的安装 在安装PostGIS前首先必须安装PostgreSQL,然后再安装好的Stack Builder中选择安装PostGIS组件.具体安装步骤可参照PostGIS的安装与初步使用 2.加载Post

  • 基于pgrouting的路径规划处理方法

    目录 一.数据处理 二.原理分析 三.效率优化 四.数据bug处理 五.后续规划 对于GIS业务来说,路径规划是非常基础的一个业务,一般公司如果处理,都会直接选择调用已经成熟的第三方的接口,比如高德.百度等.当然其实路径规划的算法非常多,像比较著名的Dijkstra.A*算法等.当然本篇文章不是介绍算法的,本文作者会根据pgrouting已经集成的Dijkstra算法来,结合postgresql数据库来处理最短路径. 一.数据处理 路径规划的核心是数据,数据是一般的路网数据,但是我们拿到路网数据

  • js正则表达式最长匹配(贪婪匹配)和最短匹配(懒惰匹配)用法分析

    本文实例分析了js正则表达式最长匹配(贪婪匹配)和最短匹配(懒惰匹配)用法.分享给大家供大家参考,具体如下: 最近在阅读RequireJS 2.1.15源码,源码开始处定义了一系列的变量,有4个正则表达式: var commentRegExp = /(\/\*([\s\S]*?)\*\/|([^:]|^)\/\/(.*)$)/mg, cjsRequireRegExp = /[^.]\s*require\s*\(\s*["']([^'"\s]+)["']\s*\)/g, jsS

  • 最短的IE判断var ie=!-[1,]分析

    以前最短的IE判定借助于IE不支持垂直制表符的特性搞出来的. 复制代码 代码如下: var ie = !+"\v1"; 仅仅需要7bytes!参见这篇文章,<32 bytes, ehr ... 9, ehr ... 7!!! to know if your browser is IE>,讲述外国人是如何把IE的判定从32 bytes一步步缩简成7 bytes!的故事但这纪录今年1月8日被一个俄国人打破了,现在只要6 bytes!它利用了IE与标准浏览器在处理数组的toStr

  • Ruby实现的最短编辑距离计算方法

    利用动态规划算法,实现最短编辑距离的计算. 复制代码 代码如下: #encoding: utf-8 #author: xu jin #date: Nov 12, 2012 #EditDistance #to find the minimum cost by using EditDistance algorithm #example output: #  "Please input a string: " #  exponential #  "Please input the

  • 解读JavaScript代码 var ie = !-[1,] 最短的IE判定代码

    var ie = !-[1,]: 这句代码在IE9之前曾被称为世界上最短的IE判定代码.代码虽短但确包含了不少javascript基础知识在里面.在这个例子中代码执行时会先调用数组的toString()方法 ,执行[1,].toString()在IE6,7,8中将会得到"1,".然后表达式就变为!-"1,".再尝试把"1,"转换成数值类型得到NaN ,再对NaN取负得到值仍为NaN.最后执行!NaN返回true.下面通过分解这个语句来回顾下代码中

  • js实现最短的XML格式化工具实例

    本文实例讲述了js实现最短的XML格式化工具的方法.分享给大家供大家参考.具体如下: 这是用 E4X 实现最短的 XML 格式化工具.可惜 IE 至今不支持这个标准特性... 请在 Firefox 或 Chrome 下运行! 1.代码如下: 复制代码 代码如下: <html>   <head>     <title>Indent XML</title>     <script language="JavaScript" type=&

  • 世界上最短的数字判断js代码

    我们知道JavaScript提供了typeof运算符,因此最容易想到的是用typeof来判断是否是number类型 function isNumber(obj) { return typeof obj === 'number' } 这个函数对于整数和浮点数都没有问题,但对于NaN值也返回true这让人感到不爽,毕竟用isNumber判断通过后谁也不会用NaN去做算术运算. 那改进一下,用Object.prototype.toString试试 function isNumber(obj) { re

随机推荐