Method for finding shortest path to destination in traaffic network using Dijkstra algorithm or Floyd-warshall algorithm

A method for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Floyd-warshall algorithm, the method comprising the steps of:

• a) computing a travel time value between two nodes for all pairs of nodes;
• b) if a left-turn restriction is included in continuous three nodes, adding a virtual node L′ in the continuous three nodes, wherein let the three nodes be nodes V, L and W;
• c) computing matrix of the pairs of nodes based on the virtual node L′;
• and
• d) finding a smallest travel time using the matrix of the pairs of nodes.

A computer-readable record media storing instructions for performing a method for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Dijkstra algorithm, the method comprising the steps of:

• a) assigning a virtual arc connection value from a starting node to a destination node based on traffic information in order to do the turn restriction, the U-turn and the P-turn, wherein the starting node indicates the starting place and the destination node indicates the destination place;
• b) selecting a smallest travel time value out of total travel time value for a temporary label node from the starting node to all nodes except for the starting node and assigning the smallest travel time value to a permanent label node;
• and
• c) determining the shortest path by tracing a permanent node stating from the destination node.

A computer-readable record media storing instructions for performing a method for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Floyd-warshall algorithm, the method comprising the steps of:

• a) computing a travel time value between two nodes for all pairs of nodes;
• b) if a left-turn restriction is included in continuous three nodes, adding a virtual node L′ in the continuous three nodes, wherein let the three nodes be nodes V, L and W;
• c) computing matrix of the pairs of nodes based on the virtual node L′;
• and
• d) finding a smallest travel time using the matrix of the pairs of nodes.