嗨，我有一系列[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

问题描述

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屋！