# 面试题

Problem one: Trains

The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!

The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.

Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.

Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).
The distance of the route A-B-C.
The distance of the route A-D.
The distance of the route A-D-C.
The distance of the route A-E-B-C-D.
The distance of the route A-E-D.
The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
The length of the shortest route (in terms of distance to travel) from A to C.
The length of the shortest route (in terms of distance to travel) from B to B.
The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.

Test Input:
For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.
Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7
Expected Output:
Output #1: 9
Output #2: 5
Output #3: 13
Output #4: 22
Output #5: NO SUCH ROUTE
Output #6: 2
Output #7: 3
Output #8: 9
Output #9: 9
Output #10: 7

# 第一天的准备

## 图论相关知识

### 图的数据结构-Java代码实现

Java邻接表表示加权有向图，附dijkstra最短路径算法

#### 节点

``````public class Vertex {

// 顶点名称
private Character name;
}
``````

#### 边

``````public class Edge {
// 边的起始节点
private Vertex startVertex;

// 边的结束节点
private Vertex endVertex;

// 边的权重  可以理解为从start到end的距离
private Integer weights;
}
``````

#### 路线

``````public class Route {
// 到初始顶点所有的路程
private List<Edge> edges = new ArrayList<>();

// 经历的路程

// 路途的总距离
private Integer distance = Algorithm.MAX;
}
``````

#### 图

``````public class WeightDirectedGraphByList {

// 图中的所有顶点数组
private List<Vertex> vertexList;

// 每个节点拥有的边的信息
private Map<Vertex, List<Edge>> vertexEdgeMap;
}
``````

``````public class WeightDirectedGraphByMatrix {

// 图中的所有顶点数组
private List<Vertex> vertexList;

// 邻接矩阵，index为顶点在List中的index，值为两顶点之间的权重
private int[][] edgeMatrix;
}
``````

### 计算图路径的相关算法

Dijkstra算法(三)之 Java详解