求助明天的面试题,大家帮看看 -----使用java语言,编写在有向图中查找最小路径的算法

Question

此有向图是由通过"标准输入"进行输入，具体的输入格式是
<n1>:<n2>:<c1>
<n3>:<n4>:<c2>
<n5>:<n6>:<c3>
..
..
..
<nm>:<nn>:<cn>
其中，每一行<n1>:<n2>:<c1>
表示从<n1>节点到<n2>节点存在一个费用为<c1>的路径此算法的输出是:从start节点到end节点找到一个费用为最小的路径，使用下面的形式输出:
start -> <m1> --> <m2> ....-> <mn> ->end: <cost>
其中<m1>,<m2>....<mn>为此路径上的节点,<cost>为此路径上总的花费如果不存在这样的路径，就输出;此题无解

Answer 1

只知道算法，嘿嘿。貌似上学的时候学过单源最短路径算法，该算法可以实现一个点到所有点的最短路径。具体算法思想大概是设置顶点集合s并不断的做贪心选择扩充这个集合。一个顶点属于集合s当且仅当从源到该顶点的路径已经。初始化时，s中只包含源，也就是start节点。设u是g的某一个顶点，把从源到u切中间只经过s中顶点的路径称为源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径。该算法每次从v-s中取出具有最短特殊路长度的顶点u添加到s中，同时对数据dist进行必要的修改。
哈哈。应该看的模模糊糊吧，去搜下单源最短路径算法吧，应该能解决你的问题。

Answer 2

节点n2到n3或者到nx没有路径吗？
最基本的图遍历问题，每个节点设置一个状态，可以采用堆栈的压栈出栈方式来处理

Answer 3

题目有个地方不明 。可以逆向么？
即：N1--N2 花C1，可以N2--N1 花C1么？

Answer 4

可以用A star寻址算法
用递归计算当前点附近每一点到终点的费用
发现不可到达的点时回朔

Answer 5

4． Shortest path in multistage graphs. Find the shortest path from 0 to 15 for the following graph.
A multistage graph is a graph (1) G=(V,E) with V partitioned into K >= 2 disjoint subsets such that if (a,b) is in E, then a is in Vi , and b is in Vi+1 for some subsets in the partition; and (2) | V1 | = | VK | = 1.
 
c语言的解法：#include<iostream>
#include<sstream>
#include<string>
#include<fstream>
using namespace std;
#define MAX 16
#define INFTY 1000void DIJKSTRA(int A[][MAX],int d[],int p[],int s)
{
   int index;
   int i,j,u=INFTY,x,y,w;
   d[s]=0;//原点到其他点的距离 
   
   int S[15],Q[15];
   for(i=1;i<=15;i++)
   {
      d[i]=INFTY;
      p[i]=-1;
      S[i]=0;
   }
    S[0]=1;//存已经纳入的点 
    i=0;
    for(w=0;w<=15;w++)//寻找距离最短的点 
    {  
        u=INFTY; 
        for(j=0;j<=15;j++)
        {
           if(A[i][j]!=INFTY)
             if(d[j]>d[i]+A[i][j])
             {
                d[j]=d[i]+A[i][j];
                p[j]=i;
            }
        }           for(x=1;x<=15;x++)
           {
            if(S[x]!=1)
            if(u>d[x])
             {
                u=d[x];
                y=x;
                //cout<<u<<"d"<<endl;
             } 
            }
             
        S[y]=1;//把最短距离的点纳入进来 
        i=y;                                
    }
    
}
void print(int p[],int end)
{
    if(p[end] == 0)
    {
        cout << end<< "->";
        return;
    }
    print(p,p[end]);
    cout << end << "->";
}int main()
{
    int A[MAX][MAX];
    int d[MAX],p[MAX]; 
    int i,j,v;
    string str;
        
    for(i=0;i<=15;i++)    
      for(j=0;j<=15;j++)
       A[i][j]=INFTY;
       
    ifstream cin("4.txt");
    while(getline(cin,str))
    {
        istringstream stream(str);
        stream>>i>>j>>v;
        A[i][j]=v;
    }
    //输入邻接矩阵结束
     
    DIJKSTRA(A,d,p,0);
    cout<<"0->";
    print(p,15);
    cout<<"15";
    getchar();
    getchar();
    getchar();
}这是现成的代码，粘贴上来，希望可以帮到你