CareerCup

Dijkstra and A*, both would give the cheapest path between the two nodes. The question though remains as to which one will do it in the least possible time.

Given good heuristics, A* will consider the fewest nodes to find the shortest path and as a result take the "least possible time".

TSP

If you mean give the routing between two random cities A and B. Then first construct a graph of all of the cities, then find the shortest path using A*.

Why Dijkstra is not allowed? Why always people use A*? What kind of weight is -ve here?

This is not TSP. Its a minimal spanning tree formation and kruskal's algorithm will provide the cheapest route for the weighted, directed graph.
read up both TSP and Minimal spanning tree on wikipedia or your favorite algorithms text book to know the difference.