嗨,我有一系列[n,n]个城市及其目的地,我怎样才能遍历并找到城市之间的最短路径 [英] Hi, I have an array of [n,n] of cities with their destination,how can I traverse and find shortest rout between cities
本文介绍了嗨,我有一系列[n,n]个城市及其目的地,我怎样才能遍历并找到城市之间的最短路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
using System;
using System.Collections.Generic;
using System.IO;
namespace TravelSmart
{
class Graph
{
List<string> cities = new List<string>();
private int[,] cost = new int[10, 10];
private int n = 0;
int infinity = 9999999;
public List<string> Cities
{
get { return cities; }
}
public int getIndex(string vname)
{
for (int i = 0; i < n; i++)
if (cities[i].Trim() == vname)
return (i);
return (-1);
}
public Graph()
{
for (int row = 0; row < n; row++)
for (int col = 0; col < n; col++)
cost[row, col] = infinity;
StreamReader reader1 = new StreamReader("Cities.txt");
string line;
while ((line = reader1.ReadLine()) != null)
cities.Add(line);
n = cities.Count;
reader1.Close();
}
public string findShortestPath(string source, string destination)
{
string result="";
int[] Distance = new int[10];
bool[] Final = new bool[10];
StreamReader reader = new StreamReader("Routs.txt");
string lines = "";
char[] separator = { '|' };
while ((lines = reader.ReadLine()) != null)
{
string[] route = lines.Split(separator);
source = route[0];
int row = getIndex(source);
destination = route[1];
int col = getIndex(destination);
int distance = Convert.ToInt32(route[2]);
cost[row, col] = distance;
//Initialize Distance Array
for (int i = 0; i < n; i++)
Distance[i] = cost[row, i];
Final[row] = true;
}
reader.Close();
for (int row = 1; row < n; row++)//n-1 passes
{
int v = 0;
for (int col= 0; col < n; col++)
{
if (Final[col] == false)
{
v = col;
break;
}
}
for (int col = 0; col < n; col++)
{
if ((Final[col] == false) && (Distance[col] < Distance[v]))
v = col;
}
Final[v] = true;
for (int w = 0; w < n; w++)
{
if (Final[w] == false)
{
if (Distance[v] + cost[v, w] < Distance[w])
Distance[w] = Distance[v] + cost[v, w];
}
}
}
for (int col = 0; col < n; col++)
{
if (Distance[col] == infinity)
{
result = source + "->" + destination + "=" + Distance[col] + " = No path";
}
else
{
result = source + "->" + destination + "=" + Distance[col] + " KM";
}
}
return result;
}
private void showMatrix()
{
for (int row = 0; row < n; row++)
{
for (int col = 0; col < n; col++)
if ((cost[row, col] != 0) && (cost[row, col] != infinity))
{
Console.Write(" " + cost[row, col]);
}
Console.WriteLine();
}
}
}
}
推荐答案
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm [ ^ ]
最短路径问题:Dijkstra算法 [ ^ ]
Dijkstra的最小距离 [ ^ ]
Dij kstra算法 [ ^ ]
Dijkstra最短路径算法的快速优先级队列实现 [ ^ ]
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm[^]
Shortest Path Problem: Dijkstra's Algorithm[^]
Dijkstra's Minimum Distance[^]
Dijkstra Algorithm[^]
A Fast Priority Queue Implementation of the Dijkstra Shortest Path Algorithm[^]
这篇关于嗨,我有一系列[n,n]个城市及其目的地,我怎样才能遍历并找到城市之间的最短路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文