如何计算两点间的最短距离

Question

如上图所示,如何计算A到E间的最短距离?
也就是说,如何让程序选择A - C - E的路线,而不是其他的?
(两点间有连线表示可以直达)

Answer 1

Dijkstra算法求最短路径(C#版) 
using System;
using System.Collections;
using System.Text;namespace Greedy
{   
    class Marx
    {
        private int[] distance;        
        private int row;
        private ArrayList ways = new ArrayList();        public Marx(int n,params int[] d)
        {
            this.row = n;
            distance = new int[row * row];
            for (int i = 0; i < row * row; i++)
            {
                this.distance[i] = d[i];              
            }
            for (int i = 0; i < this.row; i++)  //有row个点，则从中心到各点的路有row-1条
            {
                ArrayList w = new ArrayList();
                int j = 0;
                w.Add(j);
                ways.Add(w);
            }
        }
        //------------------------------
        public void Find_way()
        {
            ArrayList S = new ArrayList(1);
            ArrayList Sr = new ArrayList(1);
            int []Indexof_distance=new int[this.row];
            
            for(int i=0; i < row; i++)
            { 
                Indexof_distance[i]=i;
            }            S.Add( Indexof_distance[0] );                    for (int i = 0; i < this.row; i++)
            {
                Sr.Add( Indexof_distance[i] );
            }
            Sr.RemoveAt(0);
            int[] D = new int[this.row];    //存放中心点到每个点的距离
           
         //---------------以上已经初始化了，S和Sr(里边放的都是点的编号)------------------
            int Count = this.row - 1;
            while (Count>0)
            {
                //假定中心点的编号是0的贪吃法求路径
                for (int i = 0; i < row; i++)
                    D[i] = this.distance[i];                int min_num = (int)Sr[0];  //距中心点的最小距离点编号                foreach (int s in Sr)
                {
                    if (D[s] < D[min_num]) min_num = s;
                }
        
                //以上可以排序优化
                S.Add(min_num);
                Sr.Remove(min_num);
                //-----------把最新包含进来的点也加到路径中-------------
                ((ArrayList)ways[min_num]).Add(min_num);
                //-----------------------------------------------
                foreach (int element in Sr)
                {
                    int position = element * (this.row) + min_num;
                    bool exchange = false;      //有交换标志                    if (D[element] < D[min_num] + this.distance[position])
                        D[element] = D[element];
                    else
                    {
                        D[element] = this.distance[position] + D[min_num];
                        exchange = true;
                    }
                    //修改距离矩阵                   
                    this.distance[element] = D[element];
                    position = element * this.row;      
                    this.distance[position] = D[element];                    //修改路径---------------
                    if (exchange == true)
                    {                       
                        ((ArrayList)ways[element]).Clear();
                        foreach (int point in (ArrayList)ways[min_num])
                            ((ArrayList)ways[element]).Add(point);
                    }
                }
                --Count;
           }
        }
        //----------------------------------------------------
        public void Display()
        {         
            //------中心到各点的最短路径----------
            Console.WriteLine("中心到各点的最短路径如下: \n\n");
            int sum_d_index = 0;
            foreach(ArrayList mother in ways)
            {
                foreach (int child in mother)
                    Console.Write("V{0} -- ", child+1);
                Console.WriteLine("    路径长 {0}",distance[sum_d_index++]);
            }
        }
    }    class MainEnterPoint
    {   
        static void Main(string[] args)
        {
            int r;     //列数
            Console.Write("请输入点个数（含配送中心点）: ");
            Int32.TryParse(Console.ReadLine(), out r);
            Console.WriteLine("各点分别为: \n");
            for (int i = 0; i < r; i++)
                Console.Write("V{0} ", i);
            Console.Write("  假定第一个点是配送中心");
            Console.WriteLine("\n\n输入各点之间的距离(无通径的用个大整数表示)\n");            int[] a = new int[r * r];            
            int da;            for (int i = 0; i < r; i++)
            {
                for (int j = i + 1; j < r; j++)
                {
                    Console.Write("V{0} 到 V{1}的距离是:  ",i,j);
                    Int32.TryParse(Console.ReadLine(), out da);
                    a[i * r + j] = da;
                    Console.WriteLine();
                }
            }
            //----完善距离矩阵(距离矩阵其实可以是个上三角矩阵，
            //----但为了处理方便，还是将其完整成一个对称阵)-----------
            for (int i = 0; i < r; i++)
            {
                for (int j = 0; j < r; j++)
                {
                    if (i == j)
                    {
                        a[i * r + j] = 0;
                    }
                    a[j * r + i] = a[i * r + j];
                }
            }      
            Marx m=new Marx(r,a);
            Console.WriteLine();
            m.Find_way();
            m.Display();
        }
    }
}

Answer 2

http://zhuweisky.cnblogs.com/archive/2005/09/29/246677.aspx

Answer 3

 public static void getMinPath_Dijkstra(List<Node<int>> blues, Node<int> root)
        {
            //init
            List<Node<int>> reds = new List<Node<int>>();
            reds.Add(root);
            int blen = blues.Count;
            if (blues.Contains(root))
                blues.Remove(root);            if (blen == 0)
                return;            int[] record = new int[blen*2];            //add nearby blue node to red set
            while (blues.Count > 0)
            {
                Node<int> nearbybluenode = null;
                int minlen = int.MaxValue;
                foreach (Node<int> node in blues)
                {
                    Node<int> nearbyrednode = null;
                    int length = int.MaxValue;
                    foreach (Node<int> anode in reds)
                    {
                        if (anode.AssociatedNodes.Contains(node))
                        {
                            int len = record[anode.Value] + anode.AssociatedNodesLength[anode.AssociatedNodes.IndexOf(node)];
                            if (len < length)
                            {
                                nearbyrednode = anode;
                                length = len;
                            }
                        }
                    }
                    //record the length from blue node to the red set
                    record[node.Value] = length;
                    //record the middle node
                    if (nearbyrednode != null)
                        record[node.Value + blen] = nearbyrednode.Value;                    //record the nearby blue node
                    if (length < minlen)
                    {
                        minlen = length;
                        nearbybluenode = node;
                    }                }
                //add the nearby blue node if exist
                if (nearbybluenode != null)
                {
                    reds.Add(nearbybluenode);
                    blues.Remove(nearbybluenode);
                }
                else
                {
                    //no suited blue node found
                    break;
                }
                //print record
                foreach (int r in record)
                {
                    Console.Write((r == int.MaxValue ? "∞" : r.ToString()) + "\t");
                }
                Console.WriteLine();
            }
        }        public static void test_getMinPath_Dijkstra()
        {
            //init 10 nodes
            List<Node<int>> nodes = new List<Node<int>>();
            for (int i = 0; i < 10; i++)
                nodes.Add(new Node<int>(i));
            //init borders
            for (int k = 0; k < 9; k++)
            {
                int len = (k + 9) * (k + 9) / 10 % 100 + 1;
                nodes[k].AssociatedNodes.Add(nodes[k + 1]);
                nodes[k].AssociatedNodesLength.Add(len);                int n1 = (k + 20) * (k + 20) / 10 % 10;
                int n2 = (k + 10) * (k + 10) / 10 % 10;
                if (n1 == n2) n2 = (n2 + 2) % 10;
                if (nodes[n1].AssociatedNodes.Contains(nodes[n2]))
                    continue;
                nodes[n1].AssociatedNodes.Add(nodes[n2]);
                nodes[n1].AssociatedNodesLength.Add(len);               
            }
            //create a node that can't be connected
            nodes.Add(new Node<int>(10));            getMinPath_Dijkstra(nodes, nodes[0]);
        }

Answer 4

参考游戏中的寻路：A*(A Star)寻路：参考

Answer 5

建立一个直角坐标系，数学上不是有一个(x1-x2)^2+(y1-y2)^2然后再开方的算法吗？
原理是勾股定理
a^2+b^2=c^2x为横坐标的绝对值，y为纵坐标的绝对值
然后根据两点之间，线段最短

Answer 6

#include <iostream> 
#include <vector> 
#include <map> 
#define maxn 1010; 
using namespace std; 
typedef weight int; // double? 
int n; // n nodes 
vector <int> r[maxn]; // r[i][j]: the j-th neighbor of i 
vector <weight> e[maxn]; // e[i][j]: the length of edge i->r[i][j] 
weight dist[maxn]; 
int pa[maxn]; 
multimap <weight, int> h; 
void init() { 
    int i; 
    n=?; 
    for (i=0;i<n;i++) { 
        r[i].clear(); 
        e[i].clear(); 
    } 
    // read the graph 
} 
void dijkstra(int S) { // In the tree h, <weight, int> : <candidate distance, node id> 
    weight d, tmp; 
    int v, i, j; 
    multimap<weight, int>::iterator it; 
    h.clear(); 
    for (i=0;i<n;i++) dist[i]=-1; 
    dist[S]=0; 
    pa[S]=-1; 
    h.insert(multimap<weight, int>::value_type(0, S)); 
    while (!h.empty()) { 
        it=h.begin(); 
        v=it->second; 
        d=it->first; 
        h.erase(it); 
        for (i=0;i<r[v].size();i++) { 
            tmp=d+e[v][i]; 
            j=r[v][i]; 
            if (dist[j]<0 || tmp<dist[j]) { 
                dist[j]=tmp; 
                pa[j]=v; 
                h.insert(multimap<weight, int>::value_type(tmp, j)); 
            } 
        } 
    } 
} 
int main() { 
    return 0; 
}