Click here to Skip to main content
15,888,351 members
Please Sign up or sign in to vote.
2.00/5 (2 votes)
See more:
C#
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();
            }
        }  

    }
}
Posted
Updated 25-Oct-14 5:27am
v2

1 solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900